Prove that $\gcd(a, b) = \gcd(b, a-b)$ I can understand the concept that $\gcd(a, b) = \gcd(b, r)$, where $a = bq + r$, which is grounded from the fact that $\gcd(a, b) = \gcd(b, a-b)$, but I have no intuition for the latter.
 A: Let $d = \text{gcd}(a,b)$, then $d|a$, and $d|b$, so $d|(a-b)$, and $d|\mbox {gcd}(b,a-b)= d'$. Also $d'|b$, and $d'|(a-b)$, so $d'|(b+(a-b)) = a$, and $d'|\mbox {gcd}(a,b) = d$. So $d = d'$.
A: Lemma: $gcd(x,y)=d$ iff $d$ is the smallest natural number that can be expressed as a linear combination of $x$ and $y$ (in $\mathbb{Z}$)
We have $gcd(a,b)=d$
$d=ap+bq$ for some $p,q\in \mathbb{Z}$
$d=ap-bp+bp+bq=(a-b)p+b(p+q)=(a-b)p+bq'$ 
where $q'=p+q\in \mathbb{Z}$
Thus,
$gcd(a-b,b)=d$
A: Suppose $\gcd(a, b) = q$ it means at least that $q | a, q|b$ then $q|(a - b)$. This is true for every divisor so that for $\gcd$ also.
One user asked converse but it is also obvious. Denote $s = a - b$, then $\gcd(b, s) = \gcd(b, s + b) = \gcd(b, a)$.
A: By definition
$$gcd(a,b)=g\iff g|a,b\land (\forall h:h|a,b\implies h\le g).$$
Then
$$\begin{align}gcd(a,b)=g&\implies g|a,b\land (\forall h:h|a,b\implies h\le g)\\&\implies g|b,(a-b)\land (\forall h:h|b,(a-b)\implies h|a,b\implies h\le g)\\&\implies gcd(b,a-b)=g.\end{align}$$
A: Every common divisor of $a$ and $b$ is also a common divisor of $b$ and $a-b$.
Every common divisor of $b$ and $a-b$ is also a common divisor of $a$ and $b$, as $a=(a-b)+b$.
A: $d\mid a-b$ means $\dfrac{a-b}d=\dfrac ad-\dfrac bd$ is an integer. It's clear that if one of these fractions is an integer, then so is the other, i.e., $d\mid a\iff d\mid b$.
$d\mid\gcd(b,a-b)\implies d\mid b$, thus $d\mid a$.
Therefore a divisor of both $a-b$ and $b$ is also a divisor of $a$.
Conversely, $k\mid a$ means $\dfrac ak=\dfrac{a-b}k+\dfrac bk$ is an integer, so $k\mid a-b\iff k\mid b$.
$k\mid\gcd(a,b)\implies k\mid b$, thus $k\mid a-b$.
Therefore a divisor of both $a$ and $b$ is also a divisor of $a-b$. QED
A: Write $u=b$ and $v=a-b$. Then $a=u+v$ and $b=u$.
These two sets of equations imply that $d$ divides $u,v$ iff $d$ divides $a,b$. Therefore, $\gcd(u,v)=\gcd(a,b)$.
In algebra terms, the equations imply that $\{a,b\}$ and $\{u,v\}$ generate the same subgroup of $\mathbb Z$. It's well known that $\langle x,y \rangle = \gcd(x,y)\mathbb Z$, hence the result.
A: Forget about "greatest": let's simply look at the set of common divisors.
The set $\mathrm{CD}(a,b)$ of common divisors of $a$ and $b$ is by definition
$$
\mathrm{CD}(a,b) = \{ d \in \mathbb{Z} \colon d \text{ divides } a \text{ and } d \text{ divides } b \}.
$$
And similarly, the set $\mathrm{CD}(b,a-b)$ of common divisors of $a$ and $a-b$ is by definition
$$
\mathrm{CD}(b,a-b) = \{ d \in \mathbb{Z} \colon d \text{ divides } b \text{ and } d \text{ divides } a-b \}.
$$
In fact, we have $$\mathrm{CD}(a,b)=\mathrm{CD}(b,a-b)$$ so obviously they have the same "greatest" element (i.e., $\max\mathrm{CD}(a,b)=\max\mathrm{CD}(b,a-b)$).
To prove this, we check...


*

*If $x \in \mathrm{CD}(a,b)$, then $x$ divides both $b$ and $a-b$, so $x \in \mathrm{CD}(b,a-b)$.
Proof: By definition $x$ divides $b$.  Further, we know $x$ divides both $a$ and $b$, so $a=kx$ and $b=k'x$ for some integers $k$ and $k'$.  Thus $x$ divides $(k-k')x=a-b$.

*If $y \in \mathrm{CD}(b,a-b)$, then $y$ divides both $a$ and $b$, so $y \in \mathrm{CD}(a,b)$.
Proof: By definition $y$ divides $b$.  Further, we know $y$ divides both $b$ and $a-b$, so $b=cy$ and $a-b=c'y$ for some integers $c$ and $c'$.  Thus $y$ divides $(c-c')y=b+(a-b)=a$.
A: First of all,


*

*definition: $b|a \iff \exists k \in \mathbb{Z}: a = k \cdot b$

*Lemma 1: $a|b \wedge a|b \Rightarrow a = \pm b$

*Lemma 2: $d|a \wedge d|b \Rightarrow d|(ax + by)$, for any $x,y \in \mathbb{Z}$

*Theorem 1: If a and b are any integers, not both zero, then $gcd(a,b)$ is the smallest positive element of the set $\{ax + by: x,y \in \mathbb{Z}\}$ of linear combinations of a and b.


Thus, we need to prove $gcd(,)|gcd(,−)$ and $gcd(,−)|gcd(,)$, and as $gcd$ is always positive, they must be equal by Lemma 1.
1. $gcd(,)|gcd(,−)$
Let $d = gcd(,)$, thus $d|a \wedge d|b$ and, also, $d|(a-b)$ as it is a linear combination of $a$ and $b$ (Lemma 2).
$d|b$, $d|(a-b)$, and $gcd(,−)$ is a linear combination of $b$ and $a-b$ (Theorem 1). Therefore, $d|gcd(,−)$ by Lemma 2.
2. $gcd(,−)|gcd(,)$
Let $d = gcd(,−)$, thus $d|b \wedge d|(a-b)$.
$a = b + (a - b)$, thus $a$ is a linear combination of $b$ and $a - b$.
Therefore, $d|a$ by Lemma 2.
Again, $gcd(a,b)$ is a linear combination of $a$ and $b$ by Theorem 1, thus $d|gcd(a,b)$.
Finally, using Lemma 1:
$gcd(,)|gcd(,−) \wedge gcd(,−)|gcd(,) \Rightarrow gcd(,) = gcd(,−)$

Note that if $a = b = 0$, then $gcd(a,b) = gcd(b, a - b) = gcd(0,0) = 0$ by definition.

Proof of lemma 1
By definition, $b|a \Rightarrow |b| \leq |a|$. Therefore, $a|b \wedge b|a \Rightarrow |a| = |b| \Rightarrow a = \pm b$.
Proof of lemma 2
As $d|a \wedge d|b$, there are some integers $k_1$ and $k_2$ which meets $\frac{a}{d} = k_1$ and $\frac{b}{d} = k_2$.
Now, we need to prove $(ax + by) = k \cdot d$, for some $k \in \mathbb{Z}$.
$(ax + by) = k \cdot d \iff k = \frac{a}{d}x + \frac{b}{d}y = k_1x + k_2y$
As the multiplication of two integers is an integer, and this also follows for the sum of two integers, thus $k_1x + k_2y \in \mathbb{Z}$.
Proof of Theorem 1
This is proved at: Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to algorithms, MIT Press, 3a.
ed., 2009.
page 930, Theorem 31.2.
