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

My Solution for "If $a \equiv b \pmod n$, prove that $gcd(a, n) = gcd(b, n)$."

## 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

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

### Ranblog Newsletter

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