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