Elementary Number Theory Problems 4.2 Solution (David M. Burton's 7th Edition) - Q3
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)
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
If $a \equiv b \pmod n$, prove that $gcd(a, n) = gcd(b, n)$.
Solution
As $a \equiv b \pmod n$, we have $a - b = kn$ for some integer $k$. Let $d = gcd(a, n)$. We have $d \mid a$ and $d \mid n$, which implies that $d \mid a - kn = b$.
Let $e$ be an integer such that $e \mid b$ and $e \mid n$. Then $e \mid kn + b = a$. Since $e \mid a$ and $e \mid n$, then $e \leq d$. Therefore, $d$ is the gcd of $b$ and $n$. Thus $gcd(a, n) = gcd(b, n)$.
Read More: All My Solutions for This Book