ALGORITHM Euclid(m, n)
// Computes gcd(m, n) by Euclid’s algorithm
// Input : Two non-negative, not-both-zero integers m and n
// Output : Greatest common divisor of m and n
while n != 0 do
r <- m mod n
m <- n
n <- r
- Step 1 : If n = 0, return the value of m as the answer and stop; otherwise proceed to Step 2.
- Step 2 : Divide m by n and assign the value of the remainder to r.
- Step 3 : Assign the value of n to m and the value of r to n. Go to Step 1.
Based on applying repeatedly the equality : gcd(m, n) = gcd(n, m mod n)
Example : gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12