Euclidean Algorithm (a.k.a. GCD)

This page will use the Euclidean Algorithm to find the Greatest Common Divisor (gcd) of two numbers. The Euclidean Algorithm uses the principle that subtracting one of the numbers from the other does not change the gcd. This the same thing as repeatedly setting the larger number to the remainder of the larger number divided by the smaller number. If the gcd is 1, the two numbers are said to be coprime to each other.