Proof that $\gcd(a,b) = \gcd(\operatorname{mod}(a,b),b) $

Question

Empirically this equality holds:

$\gcd(10,8) = 2 $ and $\gcd(\operatorname{mod}(10,8),8) = \gcd(2,8) = 2 $

$\gcd(18,9) = 9 $ and $\gcd( \operatorname{mod}(18,9),9) = \gcd(0,9) = 9 $

I am stuck on how to prove it,though , and do not understand why this holds true.

Answer 1

$ \operatorname{mod}(a,b)=a-bk$ for some integer $k$. Therefore, $$\gcd( \operatorname{mod}(a,b),b)=\gcd(a-bk,b)=\gcd(a,b)$$

Would the last equality be also a problem for your?

Answer 2

$g = \gcd(a,b)$ if and only if

1. $g \mid a$.
2. $g \mid b$.
3. If $n \mid a$ and $n\mid b$ then $n \mid g$.

So suppose $g = \gcd(a,b)$.

There exists integers $q$ and $r$ such that $a = bq + r$ and $0 \le r < b$. Then $a \bmod b = r$.

To prove $g = \gcd(r, b)$, we need to show

4. $g \mid r$.
5. $g \mid b$.
6. If $n \mid r$ and $n\mid b$ then $n \mid g$.

Condition $(5.)$ is met since $g \mid b$ by condition $(2.)$. Since, by condition $(1.)$, $g \mid a$, then $g\mid a-bq=r$. Hence condition $(4.)$ is met. Finally, suppose $n \mid r$ and $n\mid b$. Then $n \mid bq+r=a$. Then condition $(3.)$ implies that $n \mid g$. So $g$ satisfies condition $(6.)$. It follows that $\gcd(a,b) = \gcd(r,b)$.