Monday, October 20, 2008

Complete Residue System

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

A set of n integers a1, a2, ..., an is a complete residue system if every integer is congruent (mod n) to exactly one of the aj'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 j1 and j2 are different integers such that:

a ≡ j1 + i (mod n)

a ≡ j2 + i (mod n)

(7) Then:

a - i ≡ j1 (mod n)

a - i ≡ j2 (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 a1, ..., an form a complete residue system (mod n), then for all integers c, the numbers b*a1+c, ..., b*an + 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 a1, ..., an be a complete residue system (mod n). [See Definition 1 above]

(3) Since ai 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) ≡ ak (mod n)

(4) Multiplying both sides by b gives us:

b*e(d-c) ≡ (d-c) ≡ b*ak (mod n)

(5) This gives us:

d ≡ b*ak + c (mod n)

(6) Since d can take on any value, it is clear that b*ak + c is onto the complete residue set. That is, for any residue (d), we can find an expression of the form b*ak + c that is congruent to it.

(7) To complete the proof, we need to show that each b*ak + 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*ai + c (mod n)

(9) Subtracting c from both sides gives:

d - c ≡ b*ai (mod n)

(10) Multiplying e to both sides gives us:

e(d-c) ≡ e*b*ai ≡ ai (mod n)

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

e(d-c) ≡ ai ≡ ak (mod n)

(12) This demonstrates that i = k.

(13) Thus, every integer is congruent to exactly one of the n integers b*a1 + c, ..., b*an + c.

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

QED

References

1 comment:

jehan said...

wow, i was looking around for good proofs of euler's formula (found yours) when I came across this blog!
definitely subscribing to this!

here's mine if you're interested- http://themathcast.blogspot.com/