Skip to main content

Congruences, Inverses and Unsafe Cancellation

What this concept is​

Write a ≡ b (mod m) when positive m divides a-b. Equal residues form equivalence classes. Addition and multiplication respect congruence, so intermediate results may be reduced modulo m. An inverse of a modulo m>1 is a residue u such that au ≡ 1 (mod m); it exists exactly when gcd(a,m)=1.

Why it matters here​

Ordinary division is not automatically legal after taking residues. An unnoticed cancellation assumption can discard valid solutions.

Concrete example​

For a=7,m=26, 15*7 - 4*26 = 1, so 15 is the canonical inverse. The extended-gcd coefficient can be reduced into [0,m).

Why exactly the coprime condition? If au + mv = 1, every common divisor divides 1, hence the gcd is 1. Conversely, extended Euclid supplies such coefficients when the gcd is 1.

For a failed cancellation, 2*1 ≡ 2*4 (mod 6) because both have remainder 2. But 1 and 4 are not congruent modulo 6. There is no inverse of 2 modulo 6.

Common confusion / misconception​

Rational 1/a is not a modular inverse. Neither a negative coefficient nor a residue greater than the modulus is automatically invalid, but APIs often require the unique canonical representative. Our inverse API excludes modulus 1 to keep the multiplicative-inverse contract explicit.

How to use it​

Before dividing a modular equation by a coefficient, compute its gcd with the modulus. If the gcd is 1, multiply by the inverse. Otherwise use the linear-congruence method in Lesson 6; do not pretend division has a unique answer.

Check yourself​

Does 5 have an inverse modulo 12? Does 6? Answers: 5 itself is an inverse; 6 has none. Verify the product and gcd in each case.

Mini drill or application​

Find the inverse of 11 modulo 26 using a Bezout certificate. Give a different counterexample to cancelling a factor not coprime to the modulus.

Read this only if stuck​

Source backbone: Mathematics for Computer Science reference. For the freely available original, use MIT’s 2015 Chapter 8 readings. See the reading guide for topic selection; chapter numbering can differ across editions.