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

My Solution for "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$..."

## Table of Contents

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

## Related Pages

### Ranblog Newsletter

Join the newsletter to receive the latest updates in your inbox.