[This page is auto-generated; please prefer to read the article’s PDF Form.]
We now make some more observations. Note that, if a > b, the assignment at (2) modifies a to a value less than b, resulting in b > a. Similarly, if b > a, assignment at (3) reverses the order to give a > b. So, if we have A≠B, i.e. if a > b or b > a when the loop starts, every iteration will do (2) or (3) alternatively, every time reversing their order. Hence, after the last iteration, we must have a > b (or b > a), with b (or a) being 0, and a (or b) being the gcd G.
The case of A = B > 0 would just result in a single iteration making b = 0 and leaving a at A = G.
For an example run of this program, consider A = 24,B = 81. The sequence of values taken by a and b will be:
| a | 24 | 24 | 6 | 6 | 0 |
| b | 81 | 9 | 9 | 3 | 3 |
resulting in b containing the gcd 3 at the end.
Copyright © 2021 Nitin Verma. All rights reserved.