# Why is the set over which we are taking the max for $\gcd(a,b)$ a subset of the set for $\gcd(a,b-a)?$

The following proof of Lemma 1.1 is from http://wstein.org/edu/2007/spring/ent/ent-html/node6.html

Proof. We only prove that $\gcd(a,b) = \gcd(a,b-a)$ , since the other cases are proved in a similar way. Suppose $d\mid a$ and $d\mid b$ , so there exist integers $c_1$ and $c_2$ such that $dc_1 = a$ and $dc_2 = b$ . Then $b - a = dc_2 - dc_1 = d(c_2-c_1)$ , so $d\mid b-a$.

Thus $\gcd(a,b)\leq \gcd(a,b-a)$ , since the set over which we are taking the max for $\gcd(a,b)$ is a subset of the set for $\gcd(a,b-a)$ . The same argument with $a$ replaced by $-a$ and $b$ replaced by $b-a$ , shows that $\gcd(a,b-a)=\gcd(-a,b-a)\leq \gcd(-a,b)=\gcd(a,b)$ , which proves that $\gcd(a,b) = \gcd(a,b-a)$.

So, I understand the reasoning in the first paragraph. Although, I thought that that the first paragraph itself would be sufficient to prove that $\gcd(a,b)= \gcd(a,b-a)$, since they share exactly the same common divisors, and thus must have the same $\gcd$. But, why does the author say "since the set over which we are taking the max for $\gcd(a,b)$ is a subset of the set for $\gcd(a,b-a)$?" I know that we're trying to prove equality, but why not say $\gcd(a,b)\geq \gcd(a,b-a)$ instead?

• You're absolutely right. The sets are the same, but proving the reverse inclusion requires a little argument, whereas the inclusion the author mentions is obvious. – Bernard Dec 3 '17 at 0:02

The first paragraph does not prove they have exactly the same common divisors. It proves that if $d$ is a common divisor of $a$ and $b$, then it is also a divisor of $b-a$, so it is a common divisor of $a$ and $b-a$. It doesn't prove the converse! There might still be common divisors of $a$ and $b-a$ that are not divisors of $b$.

If $S$ is the set of common divisors of $a$ and $b$ and $T$ is the set of common divisors of $a$ and $b-a$, then, we know that $S\subseteq T$ (but not yet that $T\subseteq S$!). This means that the greatest element of $S$ is at most the greatest element of $T$, since the greatest element of $T$ is greater then or equal to all elements of $T$ and the greatest element of $S$ is also an element of $T$. That is, $\gcd(a,b)\leq \gcd(a,b-a)$.

• For the statement, "there might still be common divisors of $a$ and $b−a$ that are not divisors of $b$ is false. I thought that at first, but upon reflection, if $d_1|a$ and $d_1|(b-a)$, then set $a=(d_1)m$ and $b-a=(d_1)*c$. We have that $b-a + a = b$, so $d_1(c) + d_1(m) = b$, thus $d_1(c+m) = b$ . Therefore common divisors of $a$ and $b-a$ are necessarily divisors of $b$ – K.M Dec 3 '17 at 0:13
• That is true, but that argument has not been given at that point in the proof. So it would be unjustified to make such an assertion at that step in the proof without giving an argument for it. – Eric Wofsey Dec 3 '17 at 0:14
• oh okay, that makes sense. thanks. – K.M Dec 3 '17 at 0:16