Sign in to watch this lesson
Advanced - Number Theory · 2:46
Linear Congruence Equations
The congruence a·x ≡ b (mod n) has a unique solution b·a⁻¹ when gcd(a, n) = 1. Otherwise, with g = gcd(a, n), the values a·x only reach multiples of g, so there is no solution unless g divides b; when it does, dividing a, b and n by g leaves an invertible equation, and the original has exactly g solutions spaced n/g apart.
You will learn
- Decide whether a·x ≡ b (mod n) is solvable from g = gcd(a, n) and b
- Solve it by dividing a, b and n by g and inverting a/g modulo n/g with extended Euclid
- List all g solutions in [0, n) as x0 + i·n/g and handle 64-bit inputs with __int128