**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**