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

Background

All theorems, corollaries, and definitions listed in the book's order:

Theorems and Corollaries in Elementary Number Theory

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 - 4)

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

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$.