|
Post by Eugene 2.0 on May 17, 2021 17:52:50 GMT
To find the greatest common divisor (GCD) for two numbers R1 and R2 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 R1 and y is R2 2) R1 divide by R2 to get the reminder of that division R3 3) R3 divide by R4 to get the reminder of that division R5 4) ... 5) if Rn = 0, then n-1 is the GCD
An example: 1349 and 1207
1) 1349 > 1207, then 1349 is R1 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 Rn = 0?
|
|