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:
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