[thaumasiotes]

It's just the Euclidean Algorithm; you call it out specifically in the OP. (Though, um, you define it incorrectly.)

I'm not sure what you're looking for with this comment:

> If someone has a better explanation of why subtracting relatively prime numbers repeatedly will always result in one, please leave a comment or reach out and help me understand better.

So I'll go through the proof that the Euclidean algorithm works, and then I'll apply the same proof to a raw subtraction ("the Euclidean Algorithm, but slower").

Step 1: for any two integers a, b, the Division Algorithm tells us there is a unique pair of integers q, r ("quotient, remainder") such that a = qb + r and 0 <= r < |b|.

Step 2: We want to find the GCD of two arbitrary integers, which we will call a and b.

Step 3: We will show that, when a = qb + r, GCD(a,b) = GCD(b,r). More explicitly, we will show that, when these two propositions are true:

    P1. z|a (in words, there is some integer m for which a = zm)
    P2. z|b

Then these two propositions are also true:

    D1. z|b
    D2. z|r

Once established, this will show that any integer evenly dividing both a and b also evenly divides both b and r, and thus GCD(a,b) = GCD(b,r).

Step 5: Getting the easy one out of the way, P2 suffices to prove D1.

Step 6: We need to show that z|r. By P1, a = zm for some integer m, and by P2, b = zn for some integer n. Then we have:

    a = qb + r
    zm = qzn + r
    r = zm - qzn = z(m-qn)

Since m, q, and n are all integers, so is (m-qn), and we have shown that z|r.

Step 7: To show that the GCDs are equal, we must also show that if z|r and z|b, then z|a. This is easy:

    a = qb + r
    a = qzm + zn = z(qm + n)

This completes the proof.

-------

Now, to apply this to subtraction.

Step 1: Instead of a = qb + r, we have the simpler equation a - b = r.

Step 2: We wish to show that given these two assumptions:

    P1. z|a
    P2. z|b

these two propositions will be true:

    D1. z|b
    D2. z|r

Step 3: P2 suffices to prove D1.

Step 4: By P1, a = zm for some integer m, and by P2, b = zn for some integer n. Then:

    a - b = r
    zm - zn = r
    z(m - n) = r

and since m and n are both integers, (m - n) is an integer and z|r.

(And in the other direction, when z|r, z|b, and a = b + r, then z|a.)

Step 5: We have now shown that GCD(a,b) = GCD(b,a-b). Iterating this process of subtracting the smaller quantity from the larger quantity will (1) necessarily form a decreasing sequence of "a" values, until r = 0; and (2) eventually yield GCD(a,b).

The GCD of two relatively prime numbers is, by definition, 1. That's why you're guaranteed to end up with (1, 0) when you apply this process to two relatively prime numbers.

(Note that since all integers evenly divide 0, GCD(a,0) = a for all a.)

[plumsempy]

Thank you very much for the proof. I can understand the proof in my analytical thoughts, but what I have a problem with is an intuition for it.

Of course it can be that I need to sit with it more, work with it more, connect more basic subjects to my intuition first to make it work. It can also be that if everyone waited for things to make intuitive sense we will fall back in science. Math is a great tool where it can take you places even when you don't possess the correct intuition if you just follow the rules.

But I have decided to try the intuition way nonetheless. My main problem is that, it was not immediately obvious to me that subtracting coprimes successively will always result in 1. It is still so strange to me. In comparison the fundamental theory of arithmetic is also strange but there is a good intuition behind it: any non prime number is a product of primes, because if it wasn't it would be prime itself!

[thaumasiotes]

> 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.

[thaumasiotes]

This comment is more to satisfy an aspect of the proof I was personally uncomfortable with.

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.

[thaumasiotes]

> In comparison the fundamental theory of arithmetic is also strange but there is a good intuition behind it: any non prime number is a product of primes, because if it wasn't it would be prime itself!

That's true, but it doesn't prove the fundamental theorem of arithmetic. You need to show that e.g. if p,q,r,s are four different primes, then pq does not equal rs.

(The important part of the theorem is that the prime factorization of an integer is unique.)

[thaumasiotes]

> (Note that since all integers evenly divide 0, GCD(a,0) = a for all a.)

Nonzero a, that is.

[aruss]

GCD(0,0) exists in any commutative ring by definition (and is not unique) :)

d is a common divisor of a,b if there exists x,y such that dx = ay, and d is a GCD of a,b if all divisors c divide d. So there exist many such x where GCD(0,0) = x (including x = 0).

[thaumasiotes]

> d is a common divisor of a,b if there exists x,y such that dx = ay

    d = 9
    a = 3
    b = 537
    x = 1
    y = 3

    dx = 9(1) = 9
    ay = 3(3) = 9 = dx

You can't actually have meant this? You're claiming that 9 is a common divisor of the pair (3, b), where b is any value. It's not even a divisor of 3.

[zodiac]

If you define GCD this way then writing gcd(a, b) = c is an abuse of notation :)