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 non-zero 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 non-zero remainder, it is the greatest common factor of 99 and 44.

Related Terms: divisor, greatest common factor (GCF), remainder

English | Espaņol