Engineering/Mathematics/Foundations of number theory

Euler's Phi Function and Fermat's Little Theorem

Counting the invertible residues modulo n produces a multiplicative function with a closed form, and Lagrange's theorem applied to that count produces the exponent identity that every public-key cryptosystem depends on.

Core theory
Number theory
Cryptographic basis
≈16 min read
Feeds RSA and Diffie–Hellman

φ(n)Units countThe number of residues coprime to n, computable instantly from the factorization — and, it is believed, not much faster than factoring without it.

a^p−1 ≡ 1FermatFor prime p and p ∤ a. The basis of every practical primality test and of the RSA correctness proof.

λ(n)True exponentCarmichael's function: the smallest exponent killing every unit. Always divides φ(n) and is often much smaller.

1, 2, 4, p^e, 2p^eCyclic moduliThe complete list of n for which ℤ*_n has a generator.

Executive summary

Euler's phi function φ(n) counts the integers in [1,n] coprime to n — equivalently, the order of the unit group ℤ*_n. Because coprimality is determined prime-by-prime, φ is multiplicative, and the Chinese remainder theorem supplies the proof in one line.

Applying Lagrange's theorem to ℤ*_n gives Euler's theorem, a^φ(n) ≡ 1, whose prime case is Fermat's little theorem. Everything downstream — RSA key equations, Fermat and Miller–Rabin primality tests, order computations, Diffie–Hellman parameter choice — is an application or a refinement of these two statements.

2Coprime residues mod 6φ(6) = 2: only 1 and 5 are invertible.

φ(p) = p−1Prime caseEvery non-zero residue is a unit, so ℤ_p is a field.

∑_d∣n φ(d) = nDivisor identityPartition the classes modulo n by the gcd with n.

λ(n) ∣ φ(n)Sharper exponentEquality holds exactly when the unit group is cyclic.

Contents

The totient function

Definition D1

Euler's phi function

φ(n) = |{a : 1 ≤ a ≤ n, gcd(a,n) = 1}| = |ℤ*_n|with the convention φ(1) = 1

Theorem T1

Multiplicativity and closed form

If gcd(m,n) = 1 then φ(mn) = φ(m)φ(n), because the CRT isomorphism ℤ_mn ≅ ℤ_m × ℤ_n restricts to a bijection of unit groups. For a prime power, φ(p^e) = p^e − p^e−1, since the non-units are exactly the multiples of p. Together:

φ(n) = n ∏_{p ∣ n} (1 − 1/p) = ∏_{p^e ∥ n} p^e−1(p−1)

Values and behaviour
n	Factorization	φ(n)	Comment
p	prime	p − 1	Maximal possible for its size
p²	prime square	p(p−1)	Non-units are the p multiples of p
pq	two distinct primes	(p−1)(q−1)	The RSA case: knowing φ(n) and n yields p and q
2^k	power of two	2^k−1	Half of all residues are odd
n with many small factors	highly composite	small relative to n	φ(n)/n can be made arbitrarily small

Density: φ(n)/n is bounded below by roughly 1/(e^γ ln ln n) for large n, so the ratio decreases only very slowly and never reaches zero.

Recovering the factorization from φ(n)

For n = pq, the pair (p,q) is the root set of X² − (n − φ(n) + 1)X + n, since p + q = n − φ(n) + 1. Computing φ(n) for such n is therefore no easier than factoring it — an equivalence that is essential to RSA's security argument.

Contents

Fermat's little theorem and Euler's theorem

Theorem T2

Euler's theorem

If gcd(a,n) = 1 then a^φ(n) ≡ 1 (mod n). Proof: ℤ*_n is a finite abelian group of order φ(n), and in any finite group the order of an element divides the order of the group.

Theorem T3

Fermat's little theorem

a^p−1 ≡ 1 (mod p) for prime p and p ∤ a; equivalently a^p ≡ a (mod p) for all aThe second form has no coprimality condition and is the version used in the AKS analysis.

Three consequences used constantly

Exponent reduction

a^e ≡ a^{e mod φ(n)} (mod n) for units. This is what makes an RSA private exponent well defined and small.

Compositeness certificate

If aⁿ⁻¹ ≢ 1 (mod n) for some a coprime to n, then n is definitely composite — proved without producing a factor.

Cheap inverses

For prime p, a⁻¹ ≡ a^p−2 (mod p). Slower than extended gcd but branch-free, which matters for constant-time code.

The converse of Fermat is false

Composites satisfying aⁿ⁻¹ ≡ 1 for a given base are pseudoprimes. Carmichael numbers — 561, 1105, 1729 and infinitely many others — satisfy it for every base coprime to n, so a Fermat test can never certify primality. The Miller–Rabin refinement exists precisely to close this gap.

Contents

The structure of ℤ*n

Knowing the order of the unit group is not the same as knowing its structure. The CRT decomposition reduces the question to prime powers:

ℤ*_n ≅ ℤ*_p₁^e₁ × ⋯ × ℤ*_{p_k^e_k}for n = p₁^e₁ ⋯ p_k^e_k, the prime-power factorization

Theorem T4

Primitive root theorem

ℤ*_n is cyclic — that is, it has a generator, called a primitive root modulo n — exactly for n ∈ {1, 2, 4, p^e, 2p^e} with p an odd prime. In particular ℤ*_p is cyclic of order p−1 for every prime p, which is the setting for Diffie–Hellman in a prime field.

Prime-power components
Modulus	Structure of the unit group	Order
p^e, p odd	cyclic	p^e−1(p−1)
2	trivial	1
4	cyclic	2
2^e, e ≥ 3	ℤ₂ × ℤ_2^e−2	2^e−1

The exceptional behaviour at powers of two is the reason the primitive root theorem has the odd-prime restriction, and the reason −1 and 2^{e−1}±1 all square to 1 modulo 2^e.

Carmichael's lambda: the exponent that actually matters

λ(n) is the smallest positive exponent with a^λ(n) ≡ 1 for all units a — the exponent of the group, given by λ(n) = lcm of the λ values of the prime-power components. It always divides φ(n), with equality precisely in the cyclic cases.

Practical consequence for RSA

For n = pq, λ(n) = lcm(p−1, q−1), which is typically about half of φ(n) = (p−1)(q−1) and can be far smaller. Choosing the private exponent modulo λ(n) rather than φ(n) gives a smaller exponent and a faster private operation, with identical correctness. Modern key formats specify this.

Contents

Orders and how to compute them

The order of a unit divides λ(n), and computing it exactly requires the factorization of that bound:

Order of α ∈ ℤ*n, given the factorization of λ(n)

input: α, λ = ∏ qᵢ^fᵢ
t ← λ
for each prime power qᵢ^fᵢ ∥ λ:
t ← t / qᵢ^fᵢ
x ← α^t mod n
while x ≠ 1: x ← x^qᵢ mod n; t ← t·qᵢ
return t // t = ord(α)

O(∑ fᵢ) modular exponentiations. Without a factorization of λ(n), no efficient method is known — order finding in ℤ*n is as hard as factoring.

Testing for a generator. g generates ℤ*_p if and only if g^(p−1)/q ≠ 1 for every prime q ∣ p−1. This needs the factorization of p−1, which is why cryptographic primes are generated together with it.
Density of generators. A fraction φ(p−1)/(p−1) of elements are generators — never less than about 1/(6 ln ln p), so random search succeeds quickly.
Order counts. In a cyclic group of order m, the number of elements of order exactly d is φ(d) for each d ∣ m, which re-proves the identity ∑_{d ∣ m} φ(d) = m.

Contents

Where these results are actually used

Application map
Setting	Result used	Role
RSA correctness	Euler's theorem	ed ≡ 1 (mod λ(n)) makes encryption and decryption inverse maps
RSA security	φ(n) ↔ factorization equivalence	Computing φ(n) is as hard as factoring n
Fermat / Miller–Rabin tests	Fermat's little theorem	Deviation from aⁿ⁻¹ ≡ 1 certifies compositeness
Diffie–Hellman parameters	Primitive root theorem	Selecting a generator of a large prime-order subgroup of ℤ*_p
Pohlig–Hellman analysis	Order divides group order	Discrete logs are easy when the order has only small prime factors
Hash and PRNG periods	Multiplicative order	The period of a multiplicative congruential generator is the order of the multiplier
AKS primality proof	a^p ≡ a (mod p)	The polynomial identity (X+a)ⁿ ≡ Xⁿ+a generalises this form

Contents

Quick reference and FAQ

Identities
Identity	Condition
φ(p) = p − 1	p prime
φ(p^e) = p^e − p^e−1	p prime
φ(mn) = φ(m)φ(n)	gcd(m,n) = 1
∑_{d ∣ n} φ(d) = n	always
a^φ(n) ≡ 1 (mod n)	gcd(a,n) = 1
a^λ(n) ≡ 1 (mod n)	gcd(a,n) = 1; λ is minimal such
λ(pq) = lcm(p−1, q−1)	p ≠ q primes
ℤ*_n cyclic	n ∈ {1,2,4,p^e,2p^e}

Can φ(n) be computed without factoring n?

No efficient method is known, and for n = pq it is provably equivalent to factoring. For small n, sieving computes φ for all values up to a bound in near-linear time, which is a different problem from evaluating it at one large argument.

Why do implementations prefer λ(n) to φ(n)?

Both give correct RSA key pairs, but λ(n) is the true group exponent, so the private exponent derived from it is smaller. Standards such as PKCS #1 define d modulo λ(n) for this reason.

Is a primitive root always small?

In practice yes — the least primitive root modulo p is typically tiny — but the best unconditional bounds are weak. Under the extended Riemann hypothesis the least primitive root is O((log p)⁶). Cryptographic code searches randomly rather than relying on such bounds.

What breaks if the modulus is a prime power instead of a product of distinct primes?

The unit group stays cyclic for odd p^e, so discrete logarithms remain well defined, but Hensel lifting makes many problems — including root extraction and discrete logs — dramatically easier than for a product of two large primes. Prime-power moduli are therefore unsuitable for RSA.

Contents

References and further reading

V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — §2.4–2.6 and §10.2.
K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer, 1990 — Chapter 4 on the structure of unit groups.
R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer, 2005 — §1.4 and §3.4.
RFC 8017 (PKCS #1 v2.2), IETF, 2016 — normative definition of RSA key parameters in terms of λ(n).

KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: euler-phi-fermat-little-theoremReview cycle: annual

Euler's Phi Function and Fermat's Little Theorem

Executive summary

The totient function

Euler's phi function

Multiplicativity and closed form

Fermat's little theorem and Euler's theorem

Euler's theorem

Fermat's little theorem

Three consequences used constantly

Exponent reduction

Compositeness certificate

Cheap inverses

The structure of ℤ*n

Primitive root theorem

Carmichael's lambda: the exponent that actually matters

Orders and how to compute them

Where these results are actually used

Quick reference and FAQ

References and further reading

Continue learning

KEVOS Intelligence

Executive summary

The totient function

Euler's phi function

Multiplicativity and closed form

Fermat's little theorem and Euler's theorem

Euler's theorem

Fermat's little theorem

Three consequences used constantly

Exponent reduction

Compositeness certificate

Cheap inverses

The structure of ℤ*n

Primitive root theorem

Carmichael's lambda: the exponent that actually matters

Orders and how to compute them

Where these results are actually used

Quick reference and FAQ

Related pages in this library

References and further reading

Continue learning