
Euclidean algorithm


A method for finding the greatest common factor of two integers. Divide the larger number using the smaller number. Repeat the division, using the remainder as the divisor, until the remainder becomes zero. The last nonzero remainder is the greatest common factor of the two integers.
For example, to find the greatest common factors of 99 and 44, we divide 44 into 99. This gives 2 with a remainder of 11. Next, divide 11 into 99, which gives 9 with a remainder of 0. Since 11 is the last nonzero remainder, it is the greatest common factor of 99 and 44.

