Euclid’s Algorithm

Screen Shot 2017-10-02 at 10.32.14 PM

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

 

Leave A Comment

Your email address will not be published. Required fields are marked *