What is Congruence?

Example 6.19 (Casting out nines)

Compatibility with $+$ and $\times$ is a checking device as old as commerce. Since $10 \equiv 1 \pmod 9$, every integer is congruent mod $9$ to its digit sum (proved as Exercise 6.2). To check the claim $1234 \times 567 = 699\,678$: digit sums give $1234 \equiv 1$ and $567 \equiv 18 \equiv 0 \pmod 9$, so the product must be $\equiv 1 \times 0 = 0$; and indeed $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$. The check passes (and the product is in fact correct). Had someone reported $699\,478$, the digit sum $43 \equiv 7 \not\equiv 0$ would convict them instantly. The test is one-sided — it catches an error unless the error is itself a multiple of $9$ — which is exactly the pseudoprime lesson of Example 6.24 in miniature: congruence checks refute, they do not certify.

Example 6.21 (Inverting $7$ modulo $26$)

Since $\gcd(7, 26) = 1$, the class of $7$ is invertible mod $26$. Extended Euclid:

then backwards:

Hence $7 \times (-11) \equiv 1 \pmod{26}$, i.e. $7^{-1} \equiv -11 \equiv 15 \pmod{26}$; check: $7 \times 15 = 105 = 4 \times 26 + 1$. With the inverse in hand, any congruence $7x \equiv c \pmod{26}$ is solved in one multiplication: $x \equiv 15c$. This mechanical inversion is the workhorse of modular arithmetic — and of the public-key protocols mentioned in Remark 6.27, where the moduli have hundreds of digits but the algorithm is exactly this one.

Example 6.22 (When the coefficient is not invertible)

Solve $12x \equiv 8 \pmod{20}$. Here $\gcd(12, 20) = 4$, so $12$ is not invertible mod $20$ — but the equation is still tractable. The congruence says $20 \mid 12x - 8$; dividing the whole relation by $4$ (divisor of all three ingredients), it is equivalent to $5 \mid 3x - 2$, i.e.

Now $\gcd(3, 5) = 1$ and $3^{-1} \equiv 2 \pmod 5$ ($3 \times 2 = 6 \equiv 1$), so $x \equiv 4 \pmod 5$: the solutions are $x \equiv 4, 9, 14, 19 \pmod{20}$ — four classes mod $20$, matching the gcd. (Had the right side not been divisible by $4$, say $12x \equiv 6 \pmod{20}$, there would be no solution at all: the left side is always $\equiv 0 \pmod 4$.) General shape: $ax \equiv b \pmod n$ is solvable iff $\gcd(a, n) \mid b$, and then has exactly $\gcd(a, n)$ solution classes — divide everything by the gcd and invert.