Question

Suppose that $a,b,c$and $r$ are integers such that $a=bq+r$. Prove each of the following statements.

(a) Every common divisor $c$of a and b is also a common divisor of $b$and $r$.

(b) Every common divisor of $b$and $r$ is also a common divisor of a and b.

(c)$\left(a,b\right)=\left(b,r\right)$

Short answer

(a)It is proved that every common divisor $c$of $a$and $b$is a common divisor of $b$and $r$.

(b)It is proved that every common divisor of $b$ and $r$ is also a common divisor of $a$and $b$.

(c)It is proved that $\left(a,b\right)=\left(b,r\right)$.

Step-by-step solution

Prove part (a) 

Assume that, $c|a$ and $c|b$, then there exist some constant integers $k,l$such that $a=ck$ and $b=cl$. Then evaluate $a=bq+r$.

$\begin{array}{rcl}ck& =& \left(cl\right)q+r\\ ck& =& clq+r\\ r& =& ck+clq\\ & =& c\left(k-lq\right)\end{array}$

Hence, $c|r$, where $c$ is a common divisor of $b$and $r$.

Prove part (b)

Assume that, $c|b$ and $c|r$, then there exist some constant integers $k,l$ such that $b=ck$ and $r=cl$. Then evaluate $a=bq+r$.

$$\begin{gathered} a=ckq+cl \\ a=c\left(kq+l\right) \end{gathered}$$

Hence, $c|a$, where $c$ is a common divisor of $b$and r.

Prove part (c) 

From part (a), $\left(a,b\right)$ is a common divisor of $b$ and $r$ as it is a common divisor of $a$and b.

Assume that $\left(a,b\right)$ is not the greatest common divisor $\left(b,r\right)$ of $b$ and $r$, then$\left(a,b\right)>\left(b,r\right)$ .

From part (b), $\left(b,r\right)$ is a common divisor of $\left(a,b\right)$, but $\left(b,r\right)$ is less than $\left(a,b\right)$, which is a contradiction of part (a).

Hence, both should be equal, that is, $\left(a,b\right)=\left(b,r\right)$.