Linear congruences
As for algebraic equations, for congruences too the problem can be posed of solving a congruence with respect to one or more variables. The simplest equation is
Definition 4.5.1. A linear congruence or linear congruence equation in the unknown x is an equation of the form
ax ≡ b (mod n)
with a, b in ℤ and n a positive integer greater than 1.
We are interested in understanding in which cases such a congruence admits solutions, intending for solution an integer x0 such that ax0 ≡n b. If a solution exists, we say that the equation is soluble.
Example 4.5.2. The equation 3x ≡ 2 (mod 9) does not admit solutions: if it did, we would find solutions in ℤ for the equation 3x + 9y = 2, but Proposition 2.19 tells us that this equation does not admit integer solutions, as gcd(3, 9) = 3, which does not divide 2.
Example 4.5.3. The equation 4x ≡ 6 (mod 10) admits the solution x = 4, which is not unique, as x = 9 is a solution too.
We now give the general conditions for a linear congruence to be solvable and, for solvable congruences, its solutions.
Proposition 4.5.4. Consider the congruence
ax ≡ b (mod n).
It admits solutions if and only if d = gcd(a, n) divides b.
Proof. To solve a linear congruence of the form ax ≡ b (mod n) we have essentially to solve a linear Diophantine equation of the form ax + ny = b. We know by Proposition 2.19 that these exist if and only if gcd(a, n) | b.□
The following proposition tells us how many solutions there are.
Proposition 4.5.5. Consider the congruence ax ≡ b (mod n) such that gcd(a, n)|b. Indicating with x0 a solution, then all numbers of the form x0 + h ⋅ n/gcd(a,n), with h ∈ ℤ, are solutions, and there are no other solutions. Among these, the solutions
x0, x0 + n/d, x0 + 2 ⋅ n/d, ..., x0 + (d − 1) ⋅ n/d (4.4)
are pairwise non-congruent and all other solutions (those with h ≥ d) are congruent to one of them. Thus the congruence admits exactly d non-congruent solutions modulo n.
Proof. Let us prove first that x0 + h ⋅ n/gcd(a,n) is a solution, for all h ∈ ℤ. We have,
a(x0 + h ⋅ n/gcd(a,n)) = ax0 + ah ⋅ n/d = ax0 + hn ≡n ax0 ≡n b.
We prove next that each solution is of this form. Let x0 and x0' be two solutions. Then
ax0 = b + hn, ax0' = b + kn,
for suitable integers h and k, so
a(x0 − x0') = (h − k)n.
By dividing both sides by d we get
a/d ⋅ (x0 − x0') = n/d ⋅ (h − k),
since a/d and n/d are coprime (see Proposition 2.22) we see that n/d divides x0 − x0', that is x0 − x0' = zn for some integer z.
We prove now that, among the solutions x0 + h ⋅ n/d, when h varies in ℤ, exactly d of them are non-congruent modulo n. To this end, we shall show that the solutions (4.4) are non-congruent modulo n and that every solution is congruent to one of them. Assume by contradiction that two of the solutions (4.4) are congruent modulo n, that is to say,
x0 + h1 ⋅ n/d ≡ x0 + h2 ⋅ n/d (mod n)
h1, h2 ∈ ℤ and 0 ≤ h1 ≤ h2 ≤ d − 1. Then we would get
h1 ⋅ n/d ≡ h2 ⋅ n/d (mod n)
hence, by dividing by n/d wchih is gcd(n/d, n), it would follow that
h1 ≡ h2 (mod n/(n/d)
yielding to a contradiction of the initial assumption 0 ≤ h1 ≤ h2 ≤ d − 1.
To prove that each solution of the form x0 + h ⋅ (n/d), when h varies in ℤ, is congruent to one of the solutions (4.4), it suffices to divide h by d, that is to say, defining h = dq + r, with 0 ≤ r ≤ d − 1, we have
x0 + h ⋅ n/d = x0 + (dq + r)m = x0 + qn + r ⋅ n/d ≡n x0 + r ⋅ n/d
which is exactly one of the solutions (4.4). □
Example 4.5.6. Consider the conguence 3x ≡ 12 (mod 15). So we have gcd(3, 15) = 3 which divides 12. One easy solution is x0 = 4. We have n/d = 5, so the solutions listed in (4.4) in this example are: x0 = 4; x0 + 1 ⋅ 5 = 9, x0 + 2 ⋅ 5 = 14. Now let's take some other value for h ≥ 3, for example h = 4: So x0 + 4 ⋅ 5 = 24. But 24 mod 15 = 9, that means x0 + 4 ⋅ 5 is congruent to x0 + 1 ⋅ 5. Any solution is congruent to ONE of those solutions: The solution with h = 3 is congruent to the one with h = 0; 19 − 5 = 15.
Corollary 4.5.7. If a and n are relatively prime gcd(a,n) = 1, then the congruence ax ≡ b (mod n) admits exactly one solution modulo n (that is any two solutions in ℤ are congruent modulo n).
The above results allow us, in particular, to find the invertible elements of ℤn, that is the elements x̄ ∈ ℤn for which an element ȳ ∈ ℤn such that x̄ȳ = 1 exists.
Corollary 4.5.8. An element ā ∈ ℤn is invertible if and only if a and n are relatively prime.
Proof. Determining the classes ā that are invertible in ℤn is equivalent to solving the congruence
ax ≡ 1 (mod n).
Now, this congruence admits a solution, and this solution is unique, if and only if GCD(a, n) = 1. So the invertible classes are the classes ā with 0 < a < n and GCD(a, n) = 1. □