Euclid’s(Euclidean) Algorithm

• Algorithm to find GCD of two large numbers

GCD(N1, N2), suppose that N1 is larger than N2

N1 = N2 * q1 + r1   <– Larger number divide by Small number

N2 = r1 * q2 + r2   <– Small number divide by remainder of previous

r1 = r2 * q3 + r3

…….

N = r * q + 0    <– When remainder becomes zero, then r is the GCD

example

• GCD(1701,3768)
  • 3768 = 1701*2 + 366
  • 1701 = 366*4 + 237
  • 366 = 237*1 + 129
  • 237 = 129*1 + 108
  • 129 = 108*1 + 21
  • 108 = 21*5  + 3
  • 21 = 3*7 + 0       <– 3 is the GCD of 1701, 3768