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

My Solution for "Prove the following statements: (a) If $gcd(a, n) = 1$, then the integers $$c, c + a, c + 2a, c + 3a, ... , c + (n - 1)a$$ form a complete set of residues modulo $n$ for any $c$. (b) Any $n$ consecutive integers form a complete set of residues modulo $n$. (c) The product of ..."

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

Prove the following statements:

(a) If $gcd(a, n) = 1$, then the integers $$c, c + a, c + 2a, c + 3a, ... , c + (n - 1)a$$ form a complete set of residues modulo $n$ for any $c$.

(b) Any $n$ consecutive integers form a complete set of residues modulo $n$.

[Hint: Use part (a).]

(c) The product of any set of $n$ consecutive integers is divisible by $n$.

## Solution

### (a)

Assume to the contrary, two of $c, c + a, c + 2a, c + 3a, ... , c + (n - 1)a$ are congruent modulo $n$. This means there exists $k$ and $j$ such that $c + ka \equiv c+ ja \pmod n$ where $0 \leq k, j \leq n - 1$ and $k \neq j$.

$c + ka \equiv c+ ja \pmod n$ means $ka \equiv ja \pmod n$. As $gcd(a, n) = 1$, using Corollary 1 of Theorem 4.3, $k \equiv j \pmod n$, which is a contradiction with $0 \leq k, j \leq n - 1$.

Therefore, if $gcd(a, n) = 1$, then the integers $$c, c + a, c + 2a, c + 3a, ... , c + (n - 1)a$$ form a complete set of residues modulo $n$ for any $c$.

## The rest is for Premium Members only (7 days free trial)

SubscribeAlready have an account? Log in