Suggested languages for you:

Americas

Europe

13

Expert-verifiedFound in: Page 14

Book edition
3rd

Author(s)
Thomas W Hungerford, David Leep

Pages
608 pages

ISBN
9781111569624

**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)$**

**(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)$ .

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$.

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$ .

$a=ckq+cl\phantom{\rule{0ex}{0ex}}a=c\left(kq+l\right)$

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

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)$ .

94% of StudySmarter users get better grades.

Sign up for free