# 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