Log In Start studying!

Select your language

Suggested languages for you:

Americas

English (US)

Europe

13

Expert-verified

Abstract Algebra: An Introduction

Found in: Page 14

Book edition 3rd

Author(s) Thomas W Hungerford, David Leep

Pages 608 pages

ISBN 9781111569624

Answers without the blur.

Just sign up for free and you're in.

Register for Free I’ll do it later

Short Answer

Suppose that $a, b, c$ and $r$ are integers such that $a = b q + 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) $(a, b) = (b, r)$

(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 $(a, b) = (b, r)$ .

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Prove part (a)

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

$\begin{array}{rcl} c k & = & (c l) q + r \\ c k & = & c l q + r \\ r & = & c k + c l q \\ = & c (k - l q) \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 = c k$ and $r = c l$ . Then evaluate $a = b q + r$ .

$a = c k q + c l a = c (k q + l)$

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

Prove part (c)

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

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

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

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

Most popular questions for Math Textbooks

Let $n$ be a positive integer. Prove that a andc leave the same remainder when divided by n if and only if $a - c = n k$ for some integerk.

If $a | (b + c)$ and $(b, c) = 1$ , prove that $(a, b) = 1 = (a, c)$ .

(a) Verify that $2^{5} - 1$ and $2^{7} - 1$ are prime.

(b) Show that $2^{11} - 1$ is not a prime.

Prove that the square of any integer a is either of the form 3k or of the form $3 k + 1$ for some integer k. [Hint: By the Division Algorithm, a must be of the form $3 q$ or $3 q + 1$ or $3 q + 2$ .]

Let $n = {p_{1}}^{r_{1}} {p_{2}}^{r_{2}} . . . {p_{k}}^{r_{k}}$ , where, $p_{1}, p_{2}, . ., p_{k}$ are distinct primes and each $r_{i} \geq 0$ . Prove that n is a perfect square if and only if each $r_{1}$ is even.

Want to see more solutions like these?

Sign up for free to discover our expert answers

Get Started - It’s free

Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.

Sign up for free