Congruences

In Depth

Two integers \(a\) and \(b\) are congruent modulo \(n\) (written \(a\equiv b\pmod{n}\)) if \(n\mid(a-b)\). Congruence is an equivalence relation that partitions the integers into \(n\) residue classes \(\{0,1,\ldots,n-1\}\). Arithmetic on residue classes forms the ring \(\mathbb{Z}/n\mathbb{Z}\).

Congruences can be added and multiplied: if \(a\equiv b\) and \(c\equiv d\pmod{n}\), then \(a+c\equiv b+d\) and \(ac\equiv bd\pmod{n}\). Division requires care: \(ac\equiv bc\pmod{n}\) implies \(a\equiv b\pmod{n/\gcd(c,n)}\), not necessarily \(\pmod{n}\).

Fermat's little theorem: if \(p\) is prime and \(\gcd(a,p)=1\), then \(a^{p-1}\equiv 1\pmod{p}\). Euler's generalization: \(a^{\phi(n)}\equiv 1\pmod{n}\) when \(\gcd(a,n)=1\). These are the basis of RSA and other public-key cryptosystems.

The Chinese Remainder Theorem (CRT) reconstructs an integer from its residues modulo pairwise coprime moduli. If \(n=p_1p_2\cdots p_k\) with distinct primes, then \(\mathbb{Z}/n\mathbb{Z}\cong\mathbb{Z}/p_1\mathbb{Z}\times\cdots\times\mathbb{Z}/p_k\mathbb{Z}\). CRT is used in fast arithmetic and in cryptographic protocols.

Quadratic congruences \(x^2\equiv a\pmod{p}\) are solvable iff \(a\) is a quadratic residue mod \(p\), determined by the Legendre symbol \((a/p)=a^{(p-1)/2}\bmod p\). The law of quadratic reciprocity relates \((p/q)\) and \((q/p)\) for odd primes \(p,q\) and is one of the most celebrated theorems in number theory.

Key Properties & Applications

Wilson's theorem: \(p\) is prime iff \((p-1)!\equiv-1\pmod{p}\). While impractical for primality testing (computing \((p-1)!\) is expensive), it is theoretically elegant and has applications in combinatorics.

The structure of \(\mathbb{Z}/n\mathbb{Z}\): it is a field iff \(n\) is prime. The group of units \((\mathbb{Z}/n\mathbb{Z})^*\) has order \(\phi(n)\) and is cyclic iff \(n=1,2,4,p^k,2p^k\). Understanding this group structure is essential for cryptographic applications.

Congruences modulo prime powers: Hensel's lemma lifts solutions of \(f(x)\equiv0\pmod{p}\) to solutions modulo \(p^k\), provided \(f'(x)\not\equiv0\pmod{p}\). This is the \(p\)-adic analogue of Newton's method and is used in solving polynomial congruences.

Further Reading & Context

The study of congruence connects to many areas of mathematics and its applications. Understanding the foundational definitions and theorems provides the basis for advanced work in analysis, algebra, and applied mathematics.

Historical development: most mathematical concepts evolved over centuries, with contributions from mathematicians across many cultures. The modern axiomatic treatment provides rigor, while computational tools enable practical application.

In modern mathematics, this topic appears in graduate courses and research across pure and applied mathematics. Connections to computer science, physics, and engineering make it a versatile and important area of study. Mastery of the core results and techniques opens doors to research in number theory, analysis, geometry, and beyond.

Recommended next steps: work through the standard theorems with full proofs, explore the connections to related topics listed above, and practice with a variety of problems ranging from computational exercises to theoretical proofs. The interplay between different areas of mathematics is one of the subject's greatest rewards.

Deep Dive: Congruence

This lesson extends core ideas for congruence with rigorous reasoning, edge-case checks, and application framing in number theory.

Practice Set

References & Editorial Notes

• Stewart, Calculus.
• Strang, Introduction to Linear Algebra.
• Apostol, Mathematical Analysis.

Last editorial review: 2026-04-14.