Math 115. More Complicated Congruences

This handout discusses congruences in more than one variable. It roughly follows what we’ve done in class with congruences in one variable.

Definition. The notation ℤ[x_{1}, …, x_{n}] means the set of all polynomials in variables x_{1}, …, x_{n} with integer coefficients.

In the following we’ll consider only a congruence f(x, y) ≡ 0 (mod m) with f ∈ ℤ[x, y] and m ∈ ℤ_{>0} . Congruences in more than two variables are handled similarly.

Throughout this handout, f ∈ ℤ[x, y] and m ∈ ℤ_{>0} .

Definition. Let f, g ∈ ℤ[x, y] . We say that f ≡ g (mod m) if all coefficients of f − g are multiples of m. This holds if and only if f − g = mh for some h ∈ ℤ[x, y] . This is an equivalence relation on ℤ[x, y] .

If f ≡ g (mod m) , then f(a, b) ≡ g(a, b) (mod m) for all a, b ∈ ℤ, so the congruences f(x, y) ≡ 0 (mod m) and g(x, y) ≡ 0 (mod m) have the same solutions.

Also, if a_{1} ≡ a_{2} (mod m) and b_{1} ≡ b_{2} (mod m) , then f(a_{1}, b_{1}) ≡ f(a_{2}, b_{2}) (mod m) , so one can describe solutions of the congruence f(x, y) ≡ 0 (mod m) by giving a subset of 𝒞 × 𝒞 , where 𝒞 is a complete residue system modulo m.

Definition. The number of solutions of a congruence f(x, y) ≡ 0 (mod m) is the number of elements of the set {(r, s) ∈ 𝒞 × 𝒞 : f(r, s) ≡ 0 (mod m)}, where 𝒞 is a complete residue system modulo m. This number is independent of the choice of 𝒞 .

One can define an equivalence relation ≡_{m} on ℤ×ℤ by saying that (a, b) ≡_{m} (a′, b′), or equivalently (a, b) ≡ (a′, b′) (mod m) , if a ≡ a′ (mod m) and b ≡ b′ (mod m) . Then the set {(a, b) ∈ ℤ × ℤ : f(a, b) ≡ 0 (mod m)} is a union of equivalence classes under this equivalence relation, and the number of solutions of f(x, y) ≡ 0 (mod m) (as defined above) is the number of these equivalence classes.

We won’t define the degree of a congruence f(x, y) ≡ 0 (mod m) . That can be defined using the same principles as one would use to define the degree of a polynomial in two (or more) variables. In other words, you first need to say what the degree of a monomial x^{i}y^{j} is (usually it’s i + j).

Now we consider the Chinese Remainder Theorem. The statements we proved about how the Chinese Remainder Theorem applies to solutions of congruences in one variable can also be proved for congruences in two (or more) variables.

To begin, let m_{1}, …, m_{t} be positive integers, pairwise relatively prime, and let m = m_{1} ⋯ m_{t}. Let 𝒞 and 𝒞_{1}, …, 𝒞_{t} be complete residue systems modulo m and modulo m_{1}, …, m_{t}, respectively. Recall that we defined a function

ψ: 𝒞 → 𝒞_{1} × ⋯ × 𝒞_{t} ,

and showed that it is bijective. Recall also that ψ was defined by ψ(r) = (r_{1}, …, r_{t}) for all r ∈ 𝒞 , where r_{i} ∈ 𝒞_{i} and r_{i} ≡ r (mod m_{i}) for all i.

To deal with congruences in two variables, we define a similar function

ψ_{2} : 𝒞 × 𝒞 → (𝒞_{1} × 𝒞_{1}) × ⋯ × (𝒞_{t} × 𝒞_{t}) ,

by letting ψ_{2}(r, s) = ((r_{1}, s_{1}), …, (r_{t}, s_{t})) for all r, s ∈ 𝒞 , where r_{i}, s_{i} ∈ 𝒞_{i}, r_{i} ≡ r (mod m_{i}) , and s_{i} ≡ s (mod m_{i}) for all i.

The function ψ_{2} is also bijective. Indeed, since its domain and codomain are finite sets with the same number m^{2} of elements, it suffices to show that it is injective. This can be done by the same method as was done for ψ. Indeed, assume that ψ_{2}(r, s) = ψ_{2}(r′, s′) , with r, s, r′, s′ ∈ 𝒞 . Let r_{i}, s_{i} for all i be as in the definition of ψ_{2}(r, s) , and let r′_{i}, s′_{i} for all i be defined similarly for ψ_{2}(r′, s′) . If ψ_{2}(r, s) = ψ_{2}(r′, s′) , then r_{i} = r′_{i} and s_{i} = s′_{i} for all i; therefore ψ(r) = (r_{1}, …, r_{t}) = (r′_{1}, …, r′_{t}) = ψ(r′) , which implies r = r′ since ψ is injective. Similarly s = s′, so (r, s) = (r′, s′) and thus ψ_{2} is injective.

Corresponding to a corollary from class on 24 September, we then have:

Corollary. Let m_{1}, …, m_{t}, m, 𝒞 , and 𝒞_{1}, …, 𝒞_{t} be as above, and let f ∈ ℤ[x, y] . Let 𝒞′ ⊆ 𝒞 × 𝒞 be the set {(r, s) ∈ 𝒞 × 𝒞 : f(r, s) ≡ 0 (mod m)}, and let

𝒞′_{i} ⊆ 𝒞_{i} × 𝒞_{i} be similarly defined for all i. Then
ψ_{2}(𝒞′) = 𝒞′_{1} × ⋯ × 𝒞′_{t} .

Proof. Let r, s ∈ 𝒞 , and let ((r_{1}, s_{1}), …, (r_{t}, s_{t})) = ψ_{2}(r, s) . Then

f(r, s) ≡ 0 (mod m) ⟺ f(r, s) ≡ 0 (mod m_{i}) ∀ i ⟺ f(r_{i}, s_{i}) ≡ 0 (mod m_{i}) ∀ i
⟺ (r_{i}, s_{i}) ∈ 𝒞′_{i} ∀ i ⟺ ψ_{2}(r, s) ∈ 𝒞′_{1} × ⋯ × 𝒞′_{t}

for the same reasons as in the earlier one-variable case. □

As a consequence, the number of solutions of the congruence f(x, y) ≡ 0 (mod m) is the product of the number of solutions (mod m_{i}) for all i, (as defined above), by the same proof as in the one-variable case.

As an example, we give another proof that, if m_{1}, m_{2} ∈ ℤ_{>0} are relatively prime, then ϕ(m_{1}m_{2}) = ϕ(m_{1})ϕ(m_{2}) , where ϕ is Euler’s totient function. Indeed, for all m > 0 , ϕ(m) is the number of solutions of the congruence xy ≡ 1 (mod m) (the proof is left to you as an exercise). Therefore we obtain the proof as an immediate consequence of the above corollary.

Finally, all of the above can also be done for systems of congruences (in the same modulus). Indeed, let f , 𝒞′, and 𝒞′_{1}, …, 𝒞′_{t} be as above. Let g ∈ ℤ[x, y] be another polynomial, and let 𝒞′′ and 𝒞′′_{1}, …, 𝒞′′_{t} be defined similarly to 𝒞′, etc., for the congruence g(x, y) ≡ 0 (mod m) and mod m_{i}, respectively. Then 𝒞′ ∩ 𝒞′′ represents the set of congruence classes of solutions of the system f(x, y) ≡ g(x, y) ≡ 0 (mod m) , and similarly 𝒞′_{i} ∩ 𝒞′′_{i} represents solutions of the same congruences mod m_{i} for all i. Therefore

ψ_{2}(𝒞′ ∩ 𝒞′′) = ψ_{2}(𝒞′) ∩ ψ_{2}(𝒞′′) = (𝒞′_{1} × ⋯ × 𝒞′_{t}) ∩ (𝒞′′_{1} × ⋯ × 𝒞′′_{t})
= (𝒞′_{1} ∩ 𝒞′′_{1}) × ⋯ × (𝒞′_{t} ∩ 𝒞′′_{t}) .