Is this a correct proof of why $\gcd(a,b) = \gcd(b, a- b)$?

Question

I have a proof but I wasn't sure if it was correct (or how rigorous it is). I will point out what worries me.

Let $D_a = \{ d : d \mid a\}$ (i.e. all elements that divide $a$) and similarly $D_b = \{ d : d \mid b\}$. Therefore we can define $\gcd(a,b)$ as follows:

$$\gcd(a,b) = \max(D_a \cap D_b)$$

Consider $D_{a-b} = \{ d : d \mid (a-b)\}$. I claim $D_{a-b} = D_a \cap D_b$. Every element that divides $a$ and $b$ should also divide the difference between $a - b$. i.e. $\forall d_{a,b} \in D_a \cap D_b$, $d_{a,b} \mid a - b$.This means that $D_{a - b}$ has at least every element that divides $a$ and $b$ i.e. $D_a \cap D_b \subseteq D_{a-b}$. I claim that $D_{a - b} \subseteq D_a \cap D_b$. Why? Consider an element $d' \in D_{a - b}$ but that doesn't divide both $a$ and $b$ but does divide the difference. Obviously, it doesn't make sense because for it to divide the difference it has to divide $a$ and $b$. Hence, the common divisors of $a$ and $b$ didn't change. Thus, $D_{a-b} = D_{a} \cap D_{b}$.

Now with that information at hand consider $\gcd(b,a-b) = \max (D_{a} \cap D_{a - b}) = \max( D_{a} \cap D_{a} \cap D_{b} ) = \max ( D_a \cap D_b ) $ which is the same as the definition of $\gcd(a,b)$.

So I was wondering if this proof was correct or if there was a way to explain it in a better or more concise way. It seems overly complicated but it actually expresses a super simple idea.

---

I think I have fixed my proof:

The idea of the proof is to show that the common divisors of $a$ and $b$ are the same as the common divisors of $b$, $a-b$ and therefore, since they share the same common divisors they share the same greatest common divisor. For this we first show that if $d \mid a$ and $d \mid b $ then $ d \mid a - b$. This is clear since if $a = x_a d$ and $b = x_b d$ then $a - b = (x_a - x_b)d$. Thus, $d \mid a - b$. So every divisor of $a$ and $b$ divides $b$ and $a - b$. For the other direction, consider an element $d'$ that divides both $b$ and $a - b$. If $d'$ divides $b$ and $b-a$ then it divides any linear combination of them, in particular, it divides the difference of them. i.e. $d' \mid a - (b -a) $ thus, $d' \mid a$. Therefore, every element that divides $b$ and $b -a$ also divides $a$ and $b$. Hence, $a, b$ and $b, b-a$ share the same common divisors and in particular they share the largest common divisor.

Answer 1

Your proof has one flaw: "Consider an element $d′∈D_{a−b}$ but that doesn't divide both $a$ and $b$ but does divide the difference. Obviously, it doesn't make sense because for it to divide the difference it has to divide $a$ and $b$.". Consider $d'=8$, $a=9$ and $b=1$.
The issue is that the statement $D_{a - b} = D_a \cap D_b$ is false. Instead, you'll want to prove that $D_{a - b} \cap D_a= D_a \cap D_b$.

How to do so:

Let $d$ be a divisor of both $a$ and $b$. Then there is $k$ and $k'$ verifying $a=dk$ and $b=dk'$. Therefore $(a-b)=d(k-k')$ i.e. $d$ divides $(a-b)$.
Then let $d$ be a divisor of both $a$ and $a-b$. Then it must divide their sum, so $d$ divides $b$.

By the way, there is minor writing issue:
One should write "$\gcd(b,a-b) = \max (D_{a} \cap D_{a - b}) $" instead of "$\gcd(b,a-b) = D_{a} \cap D_{a - b} $", since the gcd is a integer and not a set.

Answer 2

I'd go for a simpler notation: $D(a,b)=$ the set of common divisors of $a$ and $b$.

Of course, $\gcd(a,b) = \max D(a,b)$.

The result you want follows from $D(a,b) = D(a-b,b)$, which is easy to prove.