The Greatest Common Divisor algorithm allows us to determine

The \"Greatest Common Divisor\" algorithm allows us to determine the GCD of two integers without having to factor either of them This algorithm is based on the concept that whatever is the greatest divisor C of both A and B (without a reminder) must also be the greatest divisor of the difference between A and B. Proof: Assume A greaterthanorequalto B, and A = r + C and B = s + C. where r, s, and C are unknown integers. Then by factoring out C from the right hand side of equation (A - B) = (r * C - s * C) we are left with the expression (A - B) = (r - s) * C. This shows that C (the GCD of A & B) is also a factor of the difference between A and B. Since A - B is smaller than A after every iteration, we keep applying this process until (A - B) = 0 and the GCD is what remains. Example: What is the GCD of 231 and 182? In step 0, A is always greater than or equal to B. In steps 1 and beyond, the A value is the greater of the prior step\'s B or (A-B) values. The B value is the lesser of either the prior step\'s B or (A - B) values. The algorithm stops when A - B = 0, and the GCD was the very last B value. Follow along with each step in the table below: What is the GCD of 207 and 253? Show your completed table.

Solution

GCD of 253 and 207 is 23 and the table is as under:

Step	A	B	A-B
0	253	207	46
1	207	46	161
2	161	46	115
3	115	46	69
4	69	46	23
5	46	23	23
6	23	23	0