**ALGORITHM ***Euclid*(*m*, *n*)

// Computes gcd(

m,n) by Euclid’s algorithm// Input : Two non-negative, not-both-zero integers

mandn// Output : Greatest common divisor of

mandn

whilen!= 0do

r<-mmodn

m<-n

n<-r

returnm

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

Advertisements

## Leave a Reply