1
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ Prove that $\gcd(a,b)=\gcd(a+b, b)$ by the very definition of $\gcd$ and then use an immediate induction. $\endgroup$ Jul 8, 2018 at 22:18

2 Answers 2

0
$\begingroup$

$ \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?

$\endgroup$
0
$\begingroup$

$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

  1. $g \mid r$.
  2. $g \mid b$.
  3. 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)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .