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)

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

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

Related Pages

< Chapter 4.2, Q2 Chapter 4.2, Q4 >