| > I can understand the proof in my analytical thoughts, but what I have a problem with is an intuition for it. The intuition is a lot easier, to my eyes, for the subtraction. What the proof is telling you is that, if you start with a multiple of 3, and you subtract a multiple of 3, what remains will still be a multiple of 3. (And similarly for any other value of 3.) This is pretty intuitive. And as long as a and b are positive and distinct, max(b, a-b) is strictly less than max(a, b), so the iterative process produces a strictly decreasing sequence (until you get a 0 -- 0 isn't positive). So the intuition is in two or three parts: #1. Subtracting like this can never eliminate the GCD of the original pair of integers. ("Subtract one multiple of 24 from another multiple of 24, and you'll still have a multiple of 24.") #2. It can, and will, eliminate everything else. #3. If the original pair of numbers is relatively prime, their GCD is 1, so 1 is what you'll get from this process. |
We can easily show that (1) the iterative subtraction process always preserves divisibility by the GCD, and (2) it eventually reaches 0. (It cannot reach a negative value because we always subtract the smaller number from the larger number.)
It's slightly trickier to show that the process achieves the GCD before it hits zero. Theoretically, it could go from a multiple of the GCD to zero without passing through the GCD itself. This felt like a hole in my proof.
It is not the case, however:
In order to achieve r = 0, we must have had a = b at that step. We know that all of our pairs (a, b) and (b, r), at every step of the process, share the same GCD. Thus, the GCD of the original pair of numbers is equal to the GCD of the values a and b for which r = a-b = 0. Since GCD(m,m) = m for all m, this a and b are both equal to the GCD of the original pair -- which means that the process achieved the GCD.