Definition of

Euclidean Algorithm

A special way to find the greatest common factor of two integers.

With the larger number in 1st spot:
• divide the 1st number by the 2nd number. Note down the remainder.
• move the 2nd number into 1st spot, and put the remainder from the previous step in 2nd spot
• repeat until the remainder is zero

The last non-zero remainder is the greatest common factor

Example: 112 and 42
divide 112 by 42. We get 2 with a remainder of 28
divide 42 by 28. We get 1 with a remainder of 14
divide 28 by 14. We get 2 with a remainder of 0

The last non-zero remainder is 14, so the greatest common factor of 112 and 42 is 14