Euclidean Algorithm

The Euclidean Algorithm is a generalized algorithm for calculating the GCD of 2 or more numbers.

• Given GCD(A, B)
• Write A in quotient remainder form:
• Find GCD(B, R) using the Euclidean Algorithm since GCD(A, B) = GCD(B, R)
• Repeat for GCD(B, R)

For Example:
Lets say, A = 138, B = 78

Therefore GCD = 6