Complete Residue System

Definition 1: Complete Residue System (from Stark's Introduction to Number Theory)

A set of n integers a₁, a₂, ..., 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₁ and j₂ are different integers such that:

a ≡ j₁ + i (mod n)

a ≡ j₂ + i (mod n)

(7) Then:

a - i ≡ j₁ (mod n)

a - i ≡ j₂ (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₁, ..., a_n form a complete residue system (mod n), then for all integers c, the numbers b*a₁+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₁, ..., 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₁ + 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)