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

Background

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

Theorems and Corollaries in Elementary Number Theory

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 - 4)

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

Verify that if $a \equiv b \pmod {n_{1}}$ and $a \equiv b \pmod {n_{2}}$, then $a \equiv b \pmod {n}$, where the integer $n = lcm(n_{1}, n_{2})$. Hence, whenever $n_{1}$ and $n_{2}$ are relatively prime, $a \equiv b \pmod{n_{1}n_{2}}$.

Solution

From the Definition 4.1 Definition of Congruence, we know $n_{1}$ and $n_{2}$ are positive integers. Also, $n_{1} \mid a - b$ and $n_{2} \mid a - b$. So, $a- b$ is a common multiple of $n_{1}$ and $n_{2}$.

From Chapter 2.4 Q10 (c), we know "If $m$ is any common multiple of $a$ and $b$, then $lcm(a, b) \mid m$." Thus, $n \mid a - b$, which means $a \equiv b \pmod {n}$.

As both $n_{1}$ and $n_{2}$ are positive integers, we can use Theorem 2.8. When $gcd(n_{1}, n_{2}) = 1$, $lcm(n_{1}, n_{2}) = n_{1}n_{2}$. Therefore, whenever $n_{1}$ and $n_{2}$ are relatively prime, $a \equiv b \pmod {n_{1}n_{2}}$.

Read More: All My Solutions for This Book

Related Pages

< Chapter 4.2, Q12 Chapter 4.2, Q14 >