Proof of greatest common divisor 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 $?$
 A: 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)$.
A: (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$
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$.
A: 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...
