Euclid's Algorithm (The GCD)

To find the greatest common divisor (GCD) for two numbers R₁ and R₂ is through the series of divisions of them to get the GCD. Firstly, we have to find which of which is a larger number, so:

1) if x > y, then x is R₁ and y is R₂
2) R₁ divide by R₂ to get the reminder of that division R₃
3) R₃ divide by R₄ to get the reminder of that division R₅
4) ...
5) if R_n = 0, then n-1 is the GCD

An example: 1349 and 1207

1) 1349 > 1207, then 1349 is R₁ and 1207 is R2
2) 1349 / 1207 = 1(142)
3) 1207 / 142 = 8(71)
4) 142 / 71 = 2(0)
5) 2 = 0, then 71 is the GCD.

How to prove that for each two numbers there is an algorithm that has R_n = 0?