Elementary Number Theory Problems 4.2 Solution (David M. Burton's 7th Edition) - Q13
My Solution for "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}}$."
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
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
Ranblog Newsletter
Join the newsletter to receive the latest updates in your inbox.
%20-%20Q13){kind=link}