Elementary Number Theory Problems 4.2 Solution (David M. Burton's 7th Edition) - Q1

Background

All theorems, corollaries, and definitions listed in the book's order:

Theorems and Corollaries in Elementary Number Theory (Ch 1 - 3)

All theorems and corollaries mentioned in David M. Burton’s Elementary Number Theory are listed by following the book’s order. (7th Edition) (Currently Ch 1 - 3)

RanblogRan

I will only use theorems or facts that are proved before this question. So you will not see that I quote theorems or facts from the later chapters.

Question

Prove each of the following assertions:
(a) If $a \equiv b \pmod n$ and $m \mid n$, then $a \equiv b \pmod m$.
(b) If $a \equiv b \pmod n$ and $c > 0$, then $ca \equiv cb \pmod {cn}$.
(c) If $a \equiv b \pmod n$ and the integers $a$, $b$, $n$ are all divisible by $d > 0$, then $a/d \equiv b/d \pmod {n/d}$.

Solution

(a)

By the Definition of Congruence, we have $a - b = kn$ for some integer $k$. Also, $m \mid n$ implies that $n = lm$ for some integer $l$.

Then we have $a - b = k(lm) = (kl)m$. So, $a \equiv b \pmod m$.

(b)

By the Definition of Congruence, we have $a - b = kn$ for some integer $k$. As $c > 0$, we know $cn$ is a fixed positive integer. $ca - cb = ckn = k(cn)$. So, $ca \equiv cb \pmod {cn}$.

(c)

By the Definition of Congruence, we have $a - b = kn$ for some integer $k$. Since $a$, $b$, $n$ are all divisible by $d > 0$, we divide both sides by $d$ and have $\frac{a}{d} - \frac{b}{d} = k(\frac{n}{d})$.

As they are all divisible by $d > 0$, they are all integers. Also, because $d > 0$ and $n$ is a fixed positive integer by the definition already, $\frac{n}{d}$ is also a fixed positive integer. Therefore, $a/d \equiv b/d \pmod {n/d}$.

Read More: All My Solutions for This Book

Related Pages

< Chapter 3.3, Q28 Chapter 4.2, Q2 >