maths2u
PhysicsMathsChemistryBiology
Tier
⌕ Search ⌘K
Theorem

Euler's theorem

T-076Home MU-207Threads number
Statement

Let \(n \in \mathbb{N}\) with \(n \geq 1\), and let \(\varphi\) denote Euler's totient function, \(\varphi(n) = \#\{k \in \{1,\dots,n\} : \gcd(k,n)=1\}\). If \(a \in \mathbb{Z}\) satisfies \(\gcd(a,n) = 1\), then \[ a^{\varphi(n)} \equiv 1 \pmod n. \]

Why it matters

Euler's theorem is the master identity governing multiplicative order modulo \(n\): it says the group of units \((\mathbb{Z}/n\mathbb{Z})^\times\) is finite of order \(\varphi(n)\), and every element's order divides \(\varphi(n)\). It generalises Fermat's Little Theorem (the case \(n=p\) prime, where \(\varphi(p)=p-1\)) from prime moduli to arbitrary moduli, and it is the computational engine behind fast modular exponentiation, primality testing, and public-key cryptography.

Concretely, it is the theorem that makes RSA encryption work: decryption exponents are chosen precisely so that the composition of encryption and decryption acts as the identity modulo \(n = pq\), by an application of Euler's theorem (or its refinement via the Carmichael function).

Hypotheses
\(n\) is a positive integer. The totient \(\varphi(n)\) and the residue class ring \(\mathbb{Z}/n\mathbb{Z}\) are only defined for \(n \geq 1\); the statement is vacuous or undefined otherwise.
\(\gcd(a,n) = 1\) (a and n are coprime). Counterexample without it: take \(n = 4\), \(a = 2\) (so \(\gcd(2,4)=2 \neq 1\)). Here \(\varphi(4) = 2\), but \(2^{2} = 4 \equiv 0 \pmod 4\), not \(1\). Indeed \(a^{\varphi(n)}\) can never be \(\equiv 1 \pmod n\) when \(\gcd(a,n) \gt 1\), since then \(\gcd(a^{\varphi(n)}, n) \gt 1\) while \(\gcd(1,n)=1\).
\(a\) may be any integer, not just a residue in \(\{1,\dots,n-1\}\). This is not really an extra hypothesis but a scope clarification: the statement is about congruence classes, so replacing \(a\) by \(a+n\) changes nothing. A student who forgets this and only tests small positive \(a\) may wrongly believe the theorem needs \(a \gt 0\); e.g. \(a=-1\), \(n=5\): \(\varphi(5)=4\), \((-1)^4 = 1 \equiv 1 \pmod 5\), consistent, but negative \(a\) is not automatically excluded and the theorem holds for it too.
Proof
1
\text{Let } U_n = (\mathbb{Z}/n\mathbb{Z})^\times = \{\, \bar{x} \in \mathbb{Z}/n\mathbb{Z} : \gcd(x,n) = 1 \,\}.
Definition of the group of units of the ring \(\mathbb{Z}/n\mathbb{Z}\): a residue class \(\bar x\) is a unit (has a multiplicative inverse mod \(n\)) if and only if \(\gcd(x,n)=1\), by Bézout's identity (\(\gcd(x,n)=1 \iff \exists\, u,v \in \mathbb{Z}, ux+vn=1\), whence \(\bar u\) is the inverse of \(\bar x\)). A
2
|U_n| = \varphi(n).
Immediate from the definition of \(U_n\) in Step 1 and the definition of \(\varphi(n)\) as the count of residues in \(\{1,\dots,n\}\) coprime to \(n\): these are exactly the \(\varphi(n)\) distinct classes of \(U_n\). A
3
(U_n, \times) \text{ is a group under multiplication mod } n.
Closure: if \(\gcd(x,n)=\gcd(y,n)=1\) then \(\gcd(xy,n)=1\) (a prime dividing \(xy\) and \(n\) would divide \(x\) or \(y\) and \(n\), contradicting coprimality — Euclid's lemma). Associativity and commutativity are inherited from the ring \(\mathbb{Z}/n\mathbb{Z}\). The identity is \(\bar 1\). Every element has an inverse by Step 1 (Bézout). Hence the group axioms all hold. C
4
\gcd(a,n) = 1 \implies \bar a \in U_n.
Direct from the hypothesis and the characterisation of \(U_n\) in Step 1. A
5
\text{The map } \mu_a : U_n \to U_n, \quad \mu_a(\bar x) = \bar a \bar x, \text{ is a bijection.}
Well-defined and lands in \(U_n\) by closure (Step 3). Injective: if \(a x \equiv a x' \pmod n\) then multiplying both sides by the inverse \(a^{-1}\) (which exists by Step 1) gives \(x \equiv x' \pmod n\). A finite injective self-map of a finite set is automatically surjective (pigeonhole). Hence \(\mu_a\) permutes \(U_n\). B
6
\text{Let } U_n = \{\bar x_1, \dots, \bar x_{\varphi(n)}\} \text{ list the elements of } U_n \text{ without repetition. Then}\\ \{\bar a \bar x_1, \dots, \bar a \bar x_{\varphi(n)}\} = \{\bar x_1, \dots, \bar x_{\varphi(n)}\} \text{ as sets.}
Direct restatement of Step 5: \(\mu_a\) is a bijection of the finite list \((\bar x_1,\dots,\bar x_{\varphi(n)})\) onto itself, i.e. a permutation of its entries. B
7
\prod_{i=1}^{\varphi(n)} (\bar a \bar x_i) = \prod_{i=1}^{\varphi(n)} \bar x_i \quad \text{in } \mathbb{Z}/n\mathbb{Z}.
Two products of the same finite multiset of factors, taken in a commutative ring, are equal regardless of order — this follows because Step 6 shows the two families of factors are literally the same list up to a permutation \(\sigma\) of indices, and multiplication in \(\mathbb{Z}/n\mathbb{Z}\) is commutative and associative. A
8
\bar a^{\varphi(n)} \prod_{i=1}^{\varphi(n)} \bar x_i = \prod_{i=1}^{\varphi(n)} \bar x_i.
Left side of Step 7 rewritten: pulling the constant factor \(\bar a\) out of each of the \(\varphi(n)\) terms of the product gives \(\bar a^{\varphi(n)}\) times the product of the \(\bar x_i\), using commutativity/associativity of ring multiplication. A
9
\bar P := \prod_{i=1}^{\varphi(n)} \bar x_i \in U_n, \text{ so } \bar P \text{ is invertible in } \mathbb{Z}/n\mathbb{Z}.
\(U_n\) is closed under multiplication (Step 3, closure), so a finite product of its elements is again in \(U_n\), hence a unit by Step 1. B
10
\bar a^{\varphi(n)} \bar P = \bar P \implies \bar a^{\varphi(n)} = \bar 1.
Multiply both sides of Step 8's identity by \(\bar P^{-1}\), which exists by Step 9; this is a legal cancellation in the ring \(\mathbb{Z}/n\mathbb{Z}\) precisely because \(\bar P\) is a unit (cancelling by a non-unit, e.g. a zero divisor, would not be valid in general). B
11
a^{\varphi(n)} \equiv 1 \pmod n.
Step 10 restated in congruence notation: \(\bar a^{\varphi(n)} = \bar 1\) in \(\mathbb{Z}/n\mathbb{Z}\) means exactly \(n \mid (a^{\varphi(n)} - 1)\), which is the definition of \(a^{\varphi(n)} \equiv 1 \pmod n\). \(\blacksquare\) A
12
\text{(Alternative closing argument, via Lagrange's theorem.)} \quad \operatorname{ord}(\bar a) \mid |U_n| = \varphi(n) \implies \bar a^{\varphi(n)} = \bar 1.
Since \((U_n,\times)\) is a finite group (Step 3) and \(\bar a \in U_n\) (Step 4), the cyclic subgroup \(\langle \bar a \rangle\) generated by \(\bar a\) has order equal to the multiplicative order of \(\bar a\), and by Lagrange's theorem this order divides \(|U_n| = \varphi(n)\). Writing \(\varphi(n) = k \cdot \operatorname{ord}(\bar a)\) gives \(\bar a^{\varphi(n)} = (\bar a^{\operatorname{ord}(\bar a)})^{k} = \bar 1^{k} = \bar 1\). This reproves Step 11 as a corollary of group theory rather than the direct combinatorial argument of Steps 5–10; the two proofs are independent routes to the same conclusion. C
Result
a^{\varphi(n)} \equiv 1 \pmod n \quad \text{whenever } \gcd(a,n) = 1

Reading. Raise any integer coprime to \(n\) to the power \(\varphi(n)\), and the result always leaves remainder \(1\) on division by \(n\). Equivalently: the multiplicative order of \(a\) modulo \(n\) is a well-defined finite number that divides \(\varphi(n)\).

Scope. Holds for every modulus \(n \geq 1\) and every integer \(a\) with \(\gcd(a,n)=1\); it says nothing about \(a\) sharing a common factor with \(n\), and it does not claim \(\varphi(n)\) is the smallest such exponent (only that it is one such exponent — a multiple of the true order).

Corollaries & converses
  • Fermat's Little Theorem is the special case \(n=p\) prime: since \(\varphi(p)=p-1\), \(a^{p-1}\equiv 1 \pmod p\) for \(\gcd(a,p)=1\), and multiplying by \(a\) gives \(a^p \equiv a \pmod p\) for all integers \(a\).
  • Existence of inverses: if \(\gcd(a,n)=1\) then \(a^{\varphi(n)-1}\) is a multiplicative inverse of \(a\) modulo \(n\), since \(a \cdot a^{\varphi(n)-1} = a^{\varphi(n)} \equiv 1\).
  • Order divides totient: the multiplicative order \(\operatorname{ord}_n(a)\) always divides \(\varphi(n)\) (Step 12); this underlies primitive-root theory and index calculus.
  • Fast modular exponentiation reduction: for \(\gcd(a,n)=1\), exponents may be reduced modulo \(\varphi(n)\): \(a^{k} \equiv a^{k \bmod \varphi(n)} \pmod n\) — this is exactly the mechanism RSA relies on.
  • Converse fails: the statement "\(a^{\varphi(n)} \equiv 1 \pmod n \implies \gcd(a,n)=1\)" is true and is not really a separate converse — it is immediate since \(a^{\varphi(n)}\bar a^{-\varphi(n)}\)... more precisely, if \(a^{\varphi(n)}\equiv 1\), then \(a\) has an inverse (namely \(a^{\varphi(n)-1}\)), forcing \(\gcd(a,n)=1\). But the converse of the minimality claim fails: "the smallest \(k\) with \(a^k\equiv 1\pmod n\) equals \(\varphi(n)\)" is false in general — e.g. \(n=8\), \(a=3\): \(\varphi(8)=4\) but already \(3^2=9\equiv1\pmod8\), so the true order is \(2\), a proper divisor of \(4\).
Fails without
  • Drop coprimality \(\gcd(a,n)=1\): take \(n=6\), \(a=3\). Then \(\varphi(6)=2\) but \(3^2 = 9 \equiv 3 \pmod 6\), not \(1\). In fact \(a^k \bmod n\) can never reach \(1\) for any \(k\) once \(a\) and \(n\) share a prime factor \(p\), since then \(p \mid a^k\) for all \(k\geq 1\) but \(p \nmid 1\), so \(a^k \not\equiv 1 \pmod n\) for any positive \(k\).
  • Drop \(n \geq 1\) (allow \(n=0\)): "\(\mathbb{Z}/0\mathbb{Z}\)" is (isomorphic to) \(\mathbb{Z}\) itself, \(\varphi(0)\) is not standardly defined, and "\(a^{\varphi(0)} \equiv 1 \pmod 0\)" would demand \(a^{\varphi(0)} = 1\) as integers — false for any \(a \neq \pm1\) — so the theorem's framework collapses without a positive modulus.
  • Use a wrong exponent smaller than any valid multiple of the order (misapplication, not a hypothesis drop, but instructive): for \(n=15, a=2\) (\(\gcd(2,15)=1\), \(\varphi(15)=8\)), one has \(2^8 = 256 \equiv 1 \pmod{15}\) as guaranteed, but \(2^{4} = 16 \equiv 1 \pmod{15}\) too since the true order is \(4\); asserting \(\varphi(n)\) is always the minimal such exponent is an unjustified strengthening the theorem does not make.
Common errors
  • Applying the theorem to \(a\) sharing a factor with \(n\) (e.g. computing "\(4^{\varphi(6)} \bmod 6\)" and expecting \(1\)) — the coprimality hypothesis is silently dropped.
  • Confusing \(\varphi(n)\) with \(n-1\) for composite \(n\); e.g. assuming \(a^{n-1}\equiv 1\pmod n\) for all \(a\) coprime to \(n\) when \(n\) is not prime (this is the Fermat pseudoprimality trap — Fermat's Little Theorem's exponent \(p-1\) only equals \(\varphi(n)\) when \(n\) is prime).
  • Believing \(\varphi(n)\) is always the exact (minimal) multiplicative order of every unit, rather than merely a common multiple of all orders — see the Corollaries entry and the \(n=8\) or \(n=15\) counterexamples above.
  • Miscomputing \(\varphi(n)\) by forgetting multiplicativity requires coprime factors, e.g. wrongly using \(\varphi(mn)=\varphi(m)\varphi(n)\) when \(\gcd(m,n)\neq 1\) (it is false there, e.g. \(\varphi(4)=2\) but \(\varphi(2)\varphi(2)=1\)).
  • Treating \(a\) as required to lie in \(\{0,1,\dots,n-1\}\) or to be positive; the theorem is about the congruence class of \(a\), so any integer representative coprime to \(n\), including negative ones, works identically.
Discussion

Euler proved this result in 1763 (with the totient function itself formalised slightly later), generalising Fermat's 1640 observation for prime moduli. The conceptual leap is recognising that the residues coprime to \(n\) do not merely form a set closed under multiplication mod \(n\) — they form a group, and multiplication by any fixed unit \(a\) is a symmetry (bijection, in fact a group automorphism composed with translation... more precisely a permutation) of that group. The whole proof is an instance of a much more general fact: in any finite group \(G\), \(g^{|G|} = e\) for every \(g \in G\), which is itself an immediate corollary of Lagrange's theorem applied to the cyclic subgroup generated by \(g\). Steps 5–10 essentially reprove this special case "by hand" via the rearrangement trick, without invoking group theory abstractly, while Step 12 shows the same conclusion falls out instantly once the group-theoretic machinery (Lagrange's theorem) is available.

The theorem sits at the foundation of modern public-key cryptography. In RSA, one chooses \(n = pq\) for distinct primes \(p,q\), so \(\varphi(n) = (p-1)(q-1)\); encryption and decryption exponents \(e,d\) are chosen with \(ed \equiv 1 \pmod{\varphi(n)}\), so for any message \(a\) coprime to \(n\), \((a^e)^d = a^{ed} = a^{1 + k\varphi(n)} = a \cdot (a^{\varphi(n)})^k \equiv a \pmod n\) directly by Euler's theorem. (A more careful version of RSA's correctness argument extends this to all \(a\), not just those coprime to \(n\), using the Chinese Remainder Theorem and Fermat's Little Theorem on each prime factor separately — Euler's theorem alone only secures the coprime case cleanly.)

A sharper refinement replaces \(\varphi(n)\) by the Carmichael function \(\lambda(n)\), the exponent of the group \(U_n\) — the least common multiple of the orders of all elements, rather than the order of the whole group. Always \(\lambda(n) \mid \varphi(n)\), sometimes strictly (as the \(n=8\) and \(n=15\) examples above show), and \(a^{\lambda(n)} \equiv 1 \pmod n\) is the tightest universal statement of this shape; Euler's theorem is the coarser, more classical, and more widely taught version.

A structural remark: the proof that \(U_n\) is a group (Step 3) combined with the classification of finite abelian groups shows \(U_n\) decomposes as a direct product of cyclic groups; for odd prime powers and \(2, 4\) it is even cyclic (existence of primitive roots), while for \(2^k\), \(k\geq 3\), it is never cyclic but splits as \(\mathbb{Z}/2 \times \mathbb{Z}/2^{k-2}\). This finer structure is what ultimately explains why \(\lambda(n)\) can be strictly smaller than \(\varphi(n)\): the group's exponent (l.c.m. of cyclic factor orders) is smaller than its order whenever it fails to be cyclic. Common misconception: students often picture \(U_n\) as "the numbers coprime to \(n\)" without registering that the group operation making Euler's theorem work is multiplication mod \(n\), not addition — confusing this with the additive group \((\mathbb{Z}/n\mathbb{Z},+)\) (which has order \(n\), not \(\varphi(n)\)) is a persistent source of error.

Worked examples
1
\text{Compute } 7^{222} \bmod 15.
Set up: we want \(a^{k}\bmod n\) with \(a=7\), \(n=15\), \(k=222\). Check \(\gcd(7,15)=1\), so Euler's theorem applies. A
2
\varphi(15) = \varphi(3)\varphi(5) = (3-1)(5-1) = 2 \cdot 4 = 8.
Multiplicativity of \(\varphi\) over the coprime factorisation \(15 = 3\cdot5\), and the prime formula \(\varphi(p) = p-1\). A
3
7^{8} \equiv 1 \pmod{15}.
Direct instance of Euler's theorem with \(a=7,\ n=15,\ \varphi(n)=8\). B
4
222 = 27 \cdot 8 + 6, \quad \text{so } 7^{222} = (7^{8})^{27}\cdot 7^{6} \equiv 1^{27}\cdot 7^{6} = 7^{6} \pmod{15}.
Division algorithm to reduce the exponent modulo \(\varphi(15)=8\), then substitute Step 3. A
5
7^2 = 49 \equiv 4,\quad 7^4 \equiv 4^2 = 16 \equiv 1,\quad 7^6 = 7^4\cdot7^2 \equiv 1\cdot4 = 4 \pmod{15}.
Direct computation by repeated squaring modulo \(15\). A
7^{222} \equiv 4 \pmod{15}

Reading. Euler's theorem let us collapse a huge exponent (222) down to a small equivalent one (6) before computing, exactly the way it is used in cryptographic modular exponentiation.

1
\text{Find the inverse of } 3 \text{ modulo } 10.
Since \(\gcd(3,10)=1\), Euler's theorem guarantees an inverse exists and gives a formula for it. A
2
\varphi(10) = \varphi(2)\varphi(5) = 1 \cdot 4 = 4.
Multiplicativity of \(\varphi\) over coprime factors \(2, 5\), with \(\varphi(2)=1\), \(\varphi(5)=4\). A
3
3^{4} \equiv 1 \pmod{10} \implies 3 \cdot 3^{3} \equiv 1 \pmod{10} \implies 3^{-1} \equiv 3^{3} \pmod{10}.
Euler's theorem gives \(3^{\varphi(10)}\equiv1\); factoring out one copy of \(3\) exhibits \(3^{\varphi(10)-1}=3^3\) as an explicit inverse (Corollary "Existence of inverses" above). B
4
3^3 = 27 \equiv 7 \pmod{10}.
Direct computation. A
5
\text{Check: } 3 \cdot 7 = 21 \equiv 1 \pmod{10}. \checkmark
Verification of the claimed inverse by direct multiplication. A
3^{-1} \equiv 7 \pmod{10}

Reading. Euler's theorem does more than bound orders — it hands you a closed-form inverse \(a^{\varphi(n)-1}\) for any unit \(a\), without running the extended Euclidean algorithm.

Problems
  1. Compute \(\varphi(20)\) and use Euler's theorem to find \(3^{47} \bmod 20\).
    Solution \(20 = 4 \cdot 5\), \(\gcd(4,5)=1\), so \(\varphi(20)=\varphi(4)\varphi(5) = 2 \cdot 4 = 8\). Since \(\gcd(3,20)=1\), Euler's theorem gives \(3^8 \equiv 1 \pmod{20}\). Write \(47 = 5\cdot8 + 7\), so \(3^{47} \equiv 3^{7} \pmod{20}\). Compute: \(3^1=3\), \(3^2=9\), \(3^3=27\equiv7\), \(3^4\equiv21\equiv1\)... check: \(3^4=81\equiv1\pmod{20}\) (since \(80=4\cdot20\)). So the true order of \(3\) mod \(20\) is \(4\) (dividing \(8\), consistent with Euler). Then \(3^7 = 3^{4}\cdot3^{3} \equiv 1 \cdot 27 \equiv 7 \pmod{20}\). Answer: \(3^{47}\equiv 7\pmod{20}\).
  2. Show directly (without citing Euler's theorem) why \(5^{\varphi(9)} \not\equiv 1 \pmod 9\) is impossible to observe, i.e. verify Euler's theorem numerically for \(a=5,\ n=9\).
    Solution \(\varphi(9)=\varphi(3^2)=3^2-3^1=6\). Compute powers of \(5\) mod \(9\): \(5^1=5\), \(5^2=25\equiv7\), \(5^3\equiv35\equiv8\), \(5^4\equiv40\equiv4\), \(5^5\equiv20\equiv2\), \(5^6\equiv10\equiv1\). Indeed \(5^{6}\equiv1\pmod9\), confirming the theorem; note also that \(6\) is the exact order here (no smaller positive power gave \(1\)), an example where \(\varphi(n)\) itself is the minimal exponent.
  3. Explain why Euler's theorem cannot be used to conclude anything about \(6^{k} \bmod 9\) for any \(k\), and determine what actually happens to \(6^k \bmod 9\) as \(k \to \infty\).
    Solution \(\gcd(6,9)=3\neq1\), so the coprimality hypothesis fails and Euler's theorem simply does not apply — it makes no claim here. Directly: \(6^1=6\), \(6^2=36\equiv0\pmod9\)? Check: \(36 = 4\cdot9=36\), so \(6^2\equiv0\pmod9\). Hence \(6^k\equiv0\pmod9\) for all \(k\geq2\); the sequence is eventually constant at \(0\), never revisiting \(1\), exactly as predicted by the "Fails without" discussion (a shared prime factor forbids ever reaching \(1\)).
  4. Using Euler's theorem, prove that if \(\gcd(a,n)=1\) then the multiplicative order \(\operatorname{ord}_n(a)\) divides \(\varphi(n)\), and use this to find all possible values of \(\operatorname{ord}_7(a)\) for \(a\) coprime to \(7\).
    Solution By Euler's theorem \(a^{\varphi(n)}\equiv1\pmod n\), so the order \(d=\operatorname{ord}_n(a)\) (the least positive exponent with \(a^d\equiv1\)) satisfies: dividing \(\varphi(n)\) by \(d\) with remainder, \(\varphi(n)=qd+r\), \(0\leq r\lt d\), gives \(1\equiv a^{\varphi(n)}=(a^d)^q a^r \equiv a^r\pmod n\); by minimality of \(d\), \(r=0\), so \(d\mid\varphi(n)\). For \(n=7\) (prime), \(\varphi(7)=6\), so \(\operatorname{ord}_7(a)\) must be a divisor of \(6\): possible values are \(1,2,3,6\). (All four occur: \(\operatorname{ord}_7(1)=1\), \(\operatorname{ord}_7(6)=2\) since \(6^2=36\equiv1\), \(\operatorname{ord}_7(2)=3\) since \(2^3=8\equiv1\), and \(\operatorname{ord}_7(3)=6\), e.g. \(3\) is a primitive root mod \(7\).)
  5. A cryptography student picks \(n=pq=11\cdot13=143\) and wants to reduce \(2^{500}\bmod 143\) using Euler's theorem. Carry out the reduction, and separately verify \(\gcd(2,143)=1\) so the method is valid.
    Solution \(\gcd(2,143)=1\) since \(143=11\cdot13\) is odd. \(\varphi(143)=\varphi(11)\varphi(13)=10\cdot12=120\). By Euler's theorem \(2^{120}\equiv1\pmod{143}\). Write \(500 = 4\cdot120 + 20\), so \(2^{500}\equiv2^{20}\pmod{143}\). Compute by repeated squaring mod \(143\): \(2^{10}=1024\); \(1024 = 7\cdot143+23\), so \(2^{10}\equiv23\). Then \(2^{20}\equiv23^2=529\); \(529=3\cdot143+100\), so \(2^{20}\equiv100\pmod{143}\). Answer: \(2^{500}\equiv100\pmod{143}\).