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)

Field Extension

The content in today's blog, assumes that you feel comfortable with the idea of fields. For review of this concept, start here.

Definition 1: subfield

A set B is a subfield of a set A if both A,B are fields and B is a subset of A.

Definition 2: field extension

A set A is a field extension of a set B if B is a subfield of A.

Definition 3: R=F(u)

A field R = F(u) if and only if the following is true:

(i) u is a number that may or may not be part of the field F

(ii) For any numbers x ∈ R, there exists coefficients a₀, ..., a_n such that all a_i ∈ F and x = a₀uⁿ + a₁u^n-1 + ... + a_n.

The important idea behind Definittion 3 above is that F(u) is a field extension of F.

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001