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
- Harold M. Stark, An Introduction to Number Theory (MIT Press, 1978)
1 comment :
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/
Post a Comment