Divisibility and modular arithmetic (Phase 2 core)¶
This page is the toolbox layer for elementary number theory experiments: divisibility, gcd, congruences, residue classes, and modular inverses appear in primality testing, factorization, and prime-distribution checks.
References for standard results: [Apostol, 1976, Niven et al., 1991].
Divisibility¶
For integers \(a\) and \(b\) with \(b \ne 0\), we say \(b\) divides \(a\) (written \(b \mid a\)) if there exists an integer \(k\) such that \(a=bk\).
Basic closure rules used constantly:
If \(b\mid a\) and \(b\mid c\), then \(b\mid (a\pm c)\).
If \(b\mid a\), then \(b\mid ac\) for any integer \(c\).
If \(b\mid a\) and \(a\mid b\), then \(|a|=|b|\).
Greatest common divisor (gcd)¶
The greatest common divisor of \(a\) and \(b\), written \(\gcd(a,b)\), is the largest positive integer \(d\) such that \(d\mid a\) and \(d\mid b\).
We call \(a\) and \(b\) coprime if \(\gcd(a,b)=1\).
Bézout identity (extended gcd)¶
There exist integers \(x,y\) such that
This identity is what enables modular inverses and appears directly in many algorithms (e.g., computing inverses for modular division).
Euclidean algorithm¶
If \(a=bq+r\) with \(0\le r<|b|\), then
Repeatedly applying this step gives the Euclidean algorithm, which runs in time polynomial in the number of digits of the input.
Congruences and residue classes¶
For integers \(a,b\) and modulus \(m\ge 1\),
This is an equivalence relation; its equivalence classes are called the residue classes modulo \(m\).
In computations, we usually represent residues by integers in \(\{0,1,\dots,m-1\}\). That is a representation choice; the underlying object is the residue class.
Arithmetic modulo \(m\)¶
If \(a\equiv a'\pmod m\) and \(b\equiv b'\pmod m\), then:
\(a+b\equiv a'+b'\pmod m\)
\(ab\equiv a'b'\pmod m\)
So addition and multiplication “mod \(m\)” are well-defined.
Units and modular inverses¶
An integer \(a\) has a multiplicative inverse modulo \(m\) if and only if
In that case, there exists \(a^{-1}\) such that
In code, compute \(a^{-1}\) via the extended Euclidean algorithm (Bézout coefficients).
Important practical note: if \(\gcd(a,m)\ne 1\), then “division by \(a\) modulo \(m\)” is not defined.
Euler’s totient function and Euler’s theorem¶
Let \(\varphi(m)\) be the number of integers in \(\{1,\dots,m\}\) that are coprime to \(m\). Then Euler’s theorem states:
This generalizes Fermat’s little theorem (below) and is a conceptual bridge between congruences and multiplicative structure.
Fermat’s little theorem (FLT)¶
If \(p\) is prime and \(p\nmid a\), then
FLT motivates Fermat-style primality tests, but there are composite numbers that can still pass such tests (pseudoprimes, especially Carmichael numbers). See Carmichael numbers.
Modular exponentiation (what you implement)¶
Nearly every algorithm in this phase needs fast computation of \(a^e\bmod m\).
Use binary exponentiation (“square-and-multiply”), which evaluates \(a^e\) in \(O(\log e)\) modular multiplications.
Practical checklist for implementations:
Reduce \(a\) modulo \(m\) once at the start.
Use repeated squaring; never compute \(a^e\) as a huge integer first.
Use constant-time or side-channel-resistant variants only if you have a security goal (this project typically does not).
Chinese remainder theorem (CRT)¶
If \(m\) and \(n\) are coprime, then for any residues \(a\pmod m\) and \(b\pmod n\), there exists a unique residue \(x\pmod{mn}\) such that
Equivalently, the ring \(\mathbb{Z}/(mn)\mathbb{Z}\) “splits” into \(\mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}\) when \(\gcd(m,n)=1\).
CRT is the conceptual reason that many modular phenomena can be studied prime-power by prime-power. It is also a common proof tool for counterexamples and constructions.
How this connects to Phase 2 experiments¶
Primality tests: Fermat and Miller–Rabin use modular exponentiation and gcd checks.
Factorization: Pollard–\(\rho\) uses repeated modular iteration and gcd(\(|x-y|,n\)).
Residue classes: counting primes in residue classes is literally “arithmetic modulo \(m\)”.
Suggested related pages: