Some Number Theory

1 Linear congruences

Suppose you are given a linear congruence of the following form:

ax ≡ b (mod m)

The congruence 5x ≡ 8 (mod 18) has one solution, x = 16, the congruence 5x ≡ 8 (mod 15) has no solutions, and the congruence 5x ≡ 10 (mod 15) has five solutions, {2, 5, 8, 11, 14}. Given a linear congruence, how do you determine if there is a solution and find one if it exists? If a solution x^{∗} exists, then the modulus m must divide ax^{∗} − b, so there is some integer y such that my = ax^{∗} − b. Thus, we can write b as b = ax^{∗} − my, and we notice that the greatest common divisor of a and m, gcd(a, m), divides the right hand side of this, so it must also divide b. So, if a solutions exists, gcd(a, m) divides b. We know that there exist integers u and v such that au + mv = gcd(a, m). Now, (au+mv)(b/ gcd(a, m)) = b, so x′ = ub/ gcd(a, m) is a solution to the original congruence ax ≡ b (mod m). Thus, we get that a solution exists if and only if gcd(a, m) divides b. In fact, x′ + k(m/ gcd(a, m)) is a solution for any integer k.

2 The Chinese Remainder Theorem

Theorem 1 (The Chinese Remainder Theorem) Let m_{1}, m_{2}, ..., m_{k} be pairwise relatively prime. For any integers x_{1}, x_{2}, ..., x_{k}, there exists an integer x such that x ≡ x_{i} (mod m_{i}) for 1 ≤ i ≤ k, and this integer is uniquely determined modulo the product m = m_{1}m_{2}...m_{k}.

Not only is x uniquely determined; it is efficiently computable. The following algorithm can be used:

CRT Algorithm For 1 ≤ i ≤ k, find u_{i} such that

u_{i} ≡ 1 (mod m_{i})

u_{i} ≡ 0 (mod m_{j}) for j ≠ i

Compute x ≡ ∑_{i=1}^{k} x_{i}u_{i} (mod m).

Since u_{i} ≡ 1 (mod m_{i}) for all i, the exist integers v_{i} such that u_{i} + v_{i}m_{i} = 1. Similarly, since u_{i} ≡ 0 (mod m_{j}) for j ≠ i, there exist integers w_{i} such that u_{i} = w_{i}(m/m_{i}). Thus, w_{i}(m/m_{i}) + v_{i}m_{i} = 1, so it is easy to solve for the values v_{i} and w_{i} using the Extended Euclidean Algorithm. (Note that this is where we need that the m_{i} are pairwise relatively prime.) After each w_{i} is found, the corresponding u_{i} can be calculated. Example: Let m_{1} = 3, m_{2} = 5, and m_{3} = 7. Suppose

x_{1} ≡ 2 (mod 3)
x_{2} ≡ 3 (mod 5)
x_{3} ≡ 4 (mod 7)

To calculate u_{1}:

w_{1}(35) + v_{1}(3) = 1
w_{1} = −1; v_{1} = 12
u_{1} = (−1)35 ≡ 70 (mod 105)

To calculate u_{2}:

w_{2}(21) + v_{2}(5) = 1
w_{2} = 1; v_{2} = −4
u_{2} = (1)21 ≡ 21 (mod 105)

To calculate u_{3}:

w_{3}(15) + v_{3}(7) = 1
w_{3} = 1; v_{3} = −2
u_{1} = (1)15 ≡ 15 (mod 105)

So we can calculate x ≡ 2 · 70 + 3 · 21 + 4 · 15 ≡ 53 (mod 105).

3 The multiplicative property of the Legendre symbol

Lemma 1 Let p be an odd prime. Then exactly (p − 1)/2 of the elements of Z_{p}^{∗} are quadratic residues and (p − 1)/2 are quadratic nonresidues.

Proof : For any x ∈ Z_{p}^{∗}, (−x)^{2} ≡ (−1)^{2}x^{2} ≡ x^{2} (mod p), so no more than half of the elements are squares. Suppose that x, y ∈ Z_{p}^{∗} and x^{2} ≡ y^{2} (mod p). Then p divides (x + y)(x − y), so x ≡ −y (mod p) or x ≡ −y (mod p). Therefore, exactly half of the elements are squares. □

Theorem 2 Let p be an odd prime. Then for all integers u, v, we have (\frac{u}{p}) (\frac{v}{p}) = (\frac{uv}{p} ).

Proof : Case 1. If p divides u or p divides v, then both sides are zero. Case 2. If u and v are both quadratic residues, then there exist a, b ∈ Z_{p}^{∗} such that u ≡ a^{2} (mod p) and v ≡ b^{2} (mod p). Then, uv ≡ (ab)^{2} (mod p), so uv is also a quadratic residue. Case 3. Suppose that one of u and v is a quadratic residue and one is not. Without loss of generality, we may assume that there exists an a ∈ Z_{p}^{∗} such that u ≡ a^{2} (mod p). If uv is a quadratic residue, then there is a b ∈ Z_{p}^{∗} such that uv ≡ b^{2} (mod p), so v ≡ (ba^{−1})^{2} (mod p), contradicting the fact one of u and v is a quadratic nonresidue. Case 4. Suppose that both u and v are quadratic nonresidues. Consider the multiset S = {iu (mod p) | 1 ≤ i ≤ p − 1}. All of the elements in S are distinct, because if iu ≡ ju (mod p), then iu(u^{−1}) ≡ ju(u^{−1}) (mod p), so i ≡ j (mod p). Thus S = Z_{p}^{∗}. By case 3, if i is a quadratic residue, iu (mod p) is a quadratic nonresidue. There are (p − 1)/2 quadratic residues modulo p, so this gives us all of the (p − 1)/2) quadratic nonresidues modulo p. Thus, when i is a quadratic nonresidue modulo p, iu (mod p) is a quadratic residue. Hence, (\frac{u}{p}) (\frac{v}{p}) = 1 = (\frac{uv}{p} ). □