Solving linear congruences; Inverses

We now focus on the practical matter of how to go about finding a first solution to a linear congruence ax ≡ b (mod m) knowing its existence. For a congruence such as 20x ≡ 5 (mod 15) it is easy to spot the solution x = 1 by inspection, but the congruence 14x ≡ 11 (mod 23) doesn’t yield an obvious answer. One approach that always produces a solution is to use the idea that since d | b, we can use the Euclidean algorithm to write d = sa + tm, and then x = sb/d is a solution since

ax = (b/d)as ≡ (b/d)(as + tm) = (b/d)d = b   (mod m).

For the congruence 14x ≡ 24 (mod 45). Using the Euclidean algorithm

45 = 14 · 3 + 3;

14 = 3 · 4 + 2;

3 = 2 · 1 + 1;

2 = 2 · 1 + 0

By replacing back:

1 = 3 − 2

1 = 3 − (14 − 3 · 4)

1 = −14 + 5 · 3

1 = −14 + 5(45 − 14 · 3)

1 = 5 · 45 −16 · 14

Euclid’s algorithm produces 1 = (−16) · 14 + 5 · 45, that is, x = −16. So x = (−16) · 24 = −384, which we reduce modulo 45 by noticing −384 = −8 · 45 − 24 and (−24 + 45) = 21, to get x = 21.

Another idea to deal with a congruence such as 14x ≡ 24 (mod 45) is to factor the modulus 45 into relatively prime factors, and then solve the two congruences

14x ≡ 24 (mod 5)  and  14x ≡ 24(mod 9)

simultaneously. The first congruence reduces to 4x ≡ 4 (mod 5), which has an obvious solution x = 1, and so x = 1, 6, 11, 16, 21, . . . , are all possible solutions for the original congruence. The second congruence reduces to 5x ≡ 6 (mod 9), which has a solution x = 3, and so x = 3, 12, 21, . . . , are the solutions for the second congruence. Since 21 appears on both lists, x = 21 is the solution to the original congruence.

Inverses

We so often use one particular case of a linear congruence that it is worth discussing separately. This is the case ax ≡ 1 (mod m), where a and m are relatively prime and by Corollary 4.21, we know that this congruence has a unique solution; that is, there is a unique integer b in the complete residue system 0, 1, 2, . . . , m − 1 such that

ab ≡ 1   (mod m).

We call the integer b the inverse of a —or, also, the multiplicative inverse of a.

The reason that inverses are so useful in congruences is that they allow us to divide in situations where it might not look possible. For example, suppose we wish to solve the congruence 70 ⋅ x ≡ 8 (mod 13).

Example 4.23. Solve the congruence 14x ≡ 11 (mod 23).

Solution. We find first the inverse 14x ≡ 1 (mod 23) which is x = 5, then by multypling both sides by 5: 14 · 5x ≡ 55 (mod 23), which reduces to x ≡ 55 (mod 23), yielding to x = 9.

Example 4.24. Solve the congruence 17x2 ≡ 15 (mod 23).

Solution. We would like to divide by 17, but we can’t, because 17 ∤ 15. So, instead, we multiply by the inverse of 17; The congruence 17x ≡ 1 (mod 23), which has the solution x = 19. Therefore, modulo 23, the number 19 is the inverse of 17. If we multiply both sides by 19 we get 19 · 17x2 ≡ 19 · 15 (mod 23), which, since 19 · 17 ≡ 1 (mod 23) and 19 · 15 = 285 = 12 · 23 + 9 ≡ 9, becomes x2 ≡ 9 (mod 23). This congruence, as it happens, we can immediately solve, getting x = ±3. That is, x = 3 and x = 20. (At this point we don't know whether these are the only solutions, but we will soon introduce a theorem that guarantees this).

«Linear congruences Index System of congruences; The Chinese remainder theorem »