Suggested languages for you:

Americas

Europe

13

Expert-verified
Found in: Page 14

### Abstract Algebra: An Introduction

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

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

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

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