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

return m

Step-by-step :

  • 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