# Proof of greatest common divisor [duplicate]

This question already has an answer here:

The greatest common divisor of two positive integers $a$ and $b$ is the largest positive integer that divides both $a$ and $b$ (written $\gcd(a, b)$). For example, $\gcd(4, 6) = 2$ and $\gcd(5, 6) = 1.$

$(a)$ Prove that $\gcd(a, b) = \gcd(a, b − a).$

$(b)$ Let $r\equiv b (\mod a)$. Using part $(a)$, prove that $\gcd(a, b) = \gcd(a, r)$.

Can someone help me explain how to do this question $?$

## marked as duplicate by vadim123, Tim Raczkowski, user147263, Cameron Williams, user91500Nov 19 '15 at 5:23

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 4 Answers

(a) Say gcd$(a,b)=d$. Therefore we have that $a=dr$ and $b=ds$ where gcd$(r,s)=1$. So gcd$(a,b-a)=$gcd$(dr,d(s-r))=d$ since gcd$(r,s-r)=1$

(b) $r \equiv b \pmod a \Rightarrow a\big |r-b \Rightarrow d\big |r-ds \Rightarrow d\big |r \Rightarrow$ gcd$(a,r)=d$

If $s|a$ and $s|b-a$ , it is clear that $s|b$. This implies that every divisor of $a$ and $b-a$ is also a divisor of $b$. In particular, $gcd(a,b-a)$ divides $b$. Because of $a|gcd(a,b-a)$ we have $gcd(a,b)|gcd(a,b-a)$.

If $s|a$ and $s|b$ it is clear that $s|b-a$. This implies that every divisor of $a$ and $b$ is also a divisor of $b-a$. In particular, $gcd(a,b)$ divides $b-a$. Because of $a|gcd(a,b)$ we have $gcd(a,b-a)|gcd(a,b)$.

So, we have $gcd(a,b)|gcd(a,b-a)$ and $gcd(a,b-a)|gcd(a,b)$ implying $gcd(a,b)=gcd(a,b-a)$.

Hint: Every common divisor of $a$ and $b$ also divides $b - a$. Similarly, every common divisor of $a$ and $b - a$ also divides $b$.

HINT

(a) Let $k = \gcd(a,b)$. Since $k|a$ and $k|b$ prove $k|b-a$, so $gcd(a,b-a) \ge k$. Now assume there is a number $m>k$ such that $m | a$ and $a|b-a$ and show $m|b$ to imply that $\gcd(a,b)=m>k$, which is a contradiction...