A set of n integers a

_{1}, a

_{2}, ..., a

_{n}is a complete residue system if every integer is congruent (mod n) to exactly one of the a

_{j}'s.

In other words, a complete residue system is a one-to-one correspondence (bijection) between a set of elements the different congruence classes modulo n.

Lemma 1:

Any set of n consecutive integers is a complete residue system modulo n.

That is for any integer i, {i+0, i+1, ..., i+n-1} is a complete residue system

Proof:

(1) 0, 1, ..., n-1 is a complete residue system modulo n.

(2) Let i be any integer.

(3) For any integer a, there exists an integer j such that:

a - i ≡ j (mod n) and j ∈ {0, 1, ..., n-1}

so that:

a ≡ j + i (mod n)

(4) Since a can be any integer, this shows that j+i is "onto" the complete residue system.

(5) To complete the proof, we have to show that j+i is also "one-to-one" with the complete residue system.

(6) Suppose that j

_{1}and j

_{2}are different integers such that:

a ≡ j

_{1}+ i (mod n)

a ≡ j

_{2}+ i (mod n)

(7) Then:

a - i ≡ j

_{1}(mod n)

a - i ≡ j

_{2}(mod n)

(8) But then a -i is congruent to two distinct elements of the complete residue system which is impossible.

(9) Hence, every integer i + j is a distinct congruence class.

QED

Lemma 2:

If gcd(a,n)=1, then there exists an integer c such that ac ≡ 1 (mod n)

Proof:

(1) By Bezout's Identity (see Lemma 1, here), thre exists integers c,d such that:

ac + nd = 1.

(2) Which means that:

ac - 1 = -nd

(3) And therefore:

ac ≡ 1 (mod n)

QED

Lemma 3:

If gcd(b,n)=1 and the numbers a

_{1}, ..., a

_{n}form a complete residue system (mod n), then for all integers c, the numbers b*a

_{1}+c, ..., b*a

_{n}+ c also form a complete residue system (mod n).

Proof:

(1) By Lemma 2 above, since gcd(b,n)=1, there exists an integer e such that:

b*e ≡ 1 (mod n)

(2) Let a

_{1}, ..., a

_{n}be a complete residue system (mod n). [See Definition 1 above]

(3) Since a

_{i}is a complete residue system, For any integers c,d it follows that there exists an integer k such that 1 ≤ k ≤ n and:

e(d - c) ≡ a

_{k}(mod n)

(4) Multiplying both sides by b gives us:

b*e(d-c) ≡ (d-c) ≡ b*a

_{k}(mod n)

(5) This gives us:

d ≡ b*a

_{k}+ c (mod n)

(6) Since d can take on any value, it is clear that b*a

_{k}+ c is onto the complete residue set. That is, for any residue (d), we can find an expression of the form b*a

_{k}+ c that is congruent to it.

(7) To complete the proof, we need to show that each b*a

_{k}+ c is also one-to-one with the complete residue system.

(8) Assume that there exists an integer i such that 1 ≤ i ≤ n and:

d ≡ b*a

_{i}+ c (mod n)

(9) Subtracting c from both sides gives:

d - c ≡ b*a

_{i}(mod n)

(10) Multiplying e to both sides gives us:

e(d-c) ≡ e*b*a

_{i}≡ a

_{i}(mod n)

(11) But using step #3, we have:

e(d-c) ≡ a

_{i}≡ a

_{k}(mod n)

(12) This demonstrates that i = k.

(13) Thus, every integer is congruent to exactly one of the n integers b*a

_{1}+ c, ..., b*a

_{n}+ c.

(14) So, we have shown that this is a complete residue system (mod n).

QED

References

- Harold M. Stark,
*An Introduction to Number Theory*(MIT Press, 1978)