Congruence records equality after discarding multiples of a modulus. It turns divisibility questions into arithmetic in finite rings and makes Diophantine constraints visible through local residue information.
Residue classes
Definition. For \(n\ge1\), \[ a\equiv b\pmod n \quad\Longleftrightarrow\quad n\mid(a-b). \] The equivalence classes form the ring \(\mathbb Z/n\mathbb Z\), with addition and multiplication induced from \(\mathbb Z\).
Proposition. The class of \(a\) is a unit modulo \(n\) if and only if \(\gcd(a,n)=1\). In that case the extended Euclidean algorithm computes its inverse.
Proof. An inverse is a solution of \(ax\equiv1\pmod n\), equivalently \(ax+ny=1\). Bezout's theorem says this is solvable exactly when \(\gcd(a,n)=1\).
Linear congruences
Theorem. Let \(d=\gcd(a,n)\). The congruence \[ ax\equiv b\pmod n \] is solvable if and only if \(d\mid b\). When solvable, it has exactly \(d\) incongruent solutions modulo \(n\).
Proof. The congruence is equivalent to \(ax+ny=b\), so solvability follows from the linear Diophantine criterion. After dividing by \(d\), \(a/d\) is invertible modulo \(n/d\), giving one class modulo \(n/d\). It lifts to the \(d\) classes \(x_0+k(n/d)\), \(0\le k<d\), modulo \(n\).
Example. \(18x\equiv30\pmod{42}\) has \(d=6\). Division gives \(3x\equiv5\pmod7\), hence \(x\equiv4\pmod7\). The six solutions modulo \(42\) are \(4,11,18,25,32,39\).
Fermat and Euler
Theorem (Euler). If \(\gcd(a,n)=1\), then \[ a^{\varphi(n)}\equiv1\pmod n. \] For a prime \(p\), this gives Fermat's congruence \(a^{p-1}\equiv1\pmod p\) when \(p\nmid a\).
Proof. Multiplication by \(a\) permutes the unit classes \(u_1,\ldots,u_{\varphi(n)}\) modulo \(n\). Therefore \[ a^{\varphi(n)}u_1\cdots u_{\varphi(n)} \equiv u_1\cdots u_{\varphi(n)}\pmod n. \] The product is a unit and can be cancelled.
Polynomial congruences
Proposition. A nonzero polynomial of degree \(d\) over a field has at most \(d\) roots. In particular, a polynomial modulo a prime has at most its degree many roots unless all coefficients vanish modulo that prime.
Proof. If \(f(a)=0\), polynomial division gives \(f(x)=(x-a)g(x)\). Every other root is a root of \(g\); induct on degree.
The field hypothesis matters. Modulo \(8\), the polynomial \(x^2-1\) has four roots \(1,3,5,7\), more than its degree, because \(\mathbb Z/8\mathbb Z\) has zero divisors.