Euler's Theorem

How does a computer decide, in a fraction of a second, that $7^{2019} \bmod 100 = 43$ ? It never computes the astronomically large number $7^{2019}$ . The answer rests on a single congruence discovered by Leonhard Euler in the 1760s. It is one of the most quietly powerful facts in elementary number theory. It says that raising any integer coprime to $n$ to the power $\varphi(n)$ — Euler's totient — always returns $1$ modulo $n$ . This single sentence subsumes Fermat's Little Theorem as the special case of a prime modulus. It also converts the seemingly wild problem of computing huge powers modulo $n$ into a bounded, mechanical calculation. The idea matters because modular exponentiation is the engine of modern cryptography. RSA encryption, Diffie–Hellman key exchange, and primality testing all lean on one fact. Exponents can be reduced modulo $\varphi(n)$ (or a close relative of it) without changing the answer modulo $n$ . Beyond applications, Euler's theorem is a paradigm example of something deeper. It shows how group structure — here, the group of units modulo $n$ — controls arithmetic. The proof is a masterpiece of economy. It permutes a set of residues by multiplication and reads off the answer. This technique recurs throughout algebra and number theory. The big picture is this: congruences modulo $n$ that are coprime to $n$ form a finite abelian group under multiplication. This is the group of units $(\mathbb{Z}/n\mathbb{Z})^{\times}$ , of order $\varphi(n)$ . Euler's theorem is nothing more than a special case of Lagrange's theorem from group theory. The order of every element divides the order of the group. Seen this way, it is not an isolated curiosity. Instead, it is the arithmetic shadow of a structural fact about finite groups. This article states Euler's totient function and reduced residue systems as known background. It proves Euler's theorem completely and rigorously via the classical permutation argument. It works through two nontrivial numerical examples. It shows exactly which hypothesis cannot be dropped. Finally, it points toward the finer theory of the order of an element. This concept refines Euler's theorem by asking for the smallest exponent that works.

Key takeaways

Euler's theorem: if $\gcd(a,n)=1$ then $a^{\varphi(n)} \equiv 1 \pmod{n}$ .
It generalizes Fermat's Little Theorem, which is the case $n=p$ prime, since $\varphi(p) = p-1$ .
The proof permutes a reduced residue system by multiplication by $a$ and compares products.
It reduces modular exponentiation with huge exponents to a computation modulo $\varphi(n)$ .
Coprimality $\gcd(a,n)=1$ is essential; without it the congruence can fail entirely.
Key idea: the units modulo $n$ form a group of order $\varphi(n)$ , and Euler's theorem is Lagrange's theorem in disguise.

Where this lives today

Euler's theorem is the arithmetic backbone of the RSA cryptosystem: encryption and decryption exponents are chosen so their product is congruent to $1$ modulo $\varphi(n)$ (for an RSA modulus $n = pq$ ), guaranteeing via Euler's theorem that decryption recovers the original message modulo $n$ , for any message coprime to $n$ . The theorem is also the reason why modular exponentiation algorithms used throughout cryptography and computer algebra systems can safely reduce huge exponents modulo $\varphi(n)$ before repeated squaring, turning otherwise infeasible computations into millisecond operations. In abstract algebra, Euler's theorem is the concrete number-theoretic instance of Lagrange's theorem applied to the group of units $(\mathbb{Z}/n\mathbb{Z})^{\times}$ : the order of any element of a finite group divides the order of the group, and here "order of the group" is exactly $\varphi(n)$ . This connection is the natural bridge from elementary number theory into group theory proper. In computational number theory, Euler's theorem underlies Euler pseudoprime and Fermat primality tests, which check the congruence $a^{n-1}\equiv 1 \pmod n$ (or refined variants) for random bases $a$ as a fast probabilistic filter before applying slower deterministic primality tests. In combinatorics on words and cyclic structures, the totient function and Euler's theorem appear in counting formulas such as the number of aperiodic binary necklaces, via Möbius inversion built on the same group-of-units framework. In physics and engineering, modular arithmetic governed by these same principles appears in signal processing (cyclic convolution and the discrete Fourier transform over finite fields) and in error-correcting codes, where arithmetic modulo carefully chosen $n$ exploits the predictable periodicity Euler's theorem guarantees.

Ask the tutor: How does the order of an element refine Euler's theorem, and how do we find it in practice?

n

Intuition

Think of the integers coprime to $n$ , reduced modulo $n$ , as $\varphi(n)$ labeled seats arranged in a circle — a finite, closed universe of residues that never leave the "coprime to $n$ " club under multiplication. This closure is the crucial fact: if $\gcd(a,n)=1$ and $\gcd(b,n)=1$ , then $\gcd(ab,n)=1$ too, so multiplying two units always gives a unit. Now fix $a$ coprime to $n$ and ask what happens when you multiply every seat's occupant by $a$ , modulo $n$ . Because multiplication by $a$ is invertible modulo $n$ (its inverse being any $a'$ with $aa' \equiv 1$ ), this operation cannot collide two different seats onto the same value — it must simply shuffle the seats among themselves. Multiplying all $\varphi(n)$ occupants together, then, gives the same total product as before the shuffle, just rearranged. Cancelling the common product (which is itself coprime to $n$ , hence cancellable) forces $a^{\varphi(n)} \equiv 1 \pmod n$ . This is the entire proof in miniature: a permutation argument dressed in modular arithmetic. The first figure shows this shuffle concretely for $n = 10$ , $a = 3$ : the four residues coprime to $10$ get permuted by multiplication by $3$ .

Figure

Multiplication by

a=3

permutes the reduced residue system mod

10

\{1,3,7,9\}

Because the map $x \mapsto 3x \bmod 10$ merely rearranges $\{1,3,7,9\}$ , the product $1\cdot3\cdot7\cdot9$ equals $(3\cdot1)(3\cdot3)(3\cdot7)(3\cdot9)$ modulo $10$ , and cancelling the common factor $1\cdot3\cdot7\cdot9 \equiv 189 \equiv 9$ (which is invertible mod $10$ ) leaves $3^4 \equiv 1 \pmod{10}$ — matching $\varphi(10)=4$ .

n

n \ge 1

\gcd(a,n)=1

\varphi(n) = k

p

p

Worked examples

Example 1 — reducing a large modular power. Compute $7^{2019} \bmod 100$ . First, $\gcd(7,100) = 1$ , since $7$ is prime and does not divide $100 = 2^2 \cdot 5^2$ . So Euler's theorem applies with $n = 100$ . Compute $\varphi(100)$ . Since $100 = 2^2 \cdot 5^2$ , use multiplicativity of $\varphi$ on prime powers:

\varphi(100) = \varphi(2^2)\varphi(5^2) = \big(2^2 - 2^1\big)\big(5^2 - 5^1\big) = (4-2)(25-5) = 2 \cdot 20 = 40.

By Euler's theorem, $7^{40} \equiv 1 \pmod{100}$ . Now reduce the exponent $2019$ modulo $40$ :

2019 = 40 \cdot 50 + 19, \qquad \text{so} \qquad 2019 \equiv 19 \pmod{40}.

Hence

7^{2019} = 7^{40 \cdot 50 + 19} = \big(7^{40}\big)^{50} \cdot 7^{19} \equiv 1^{50}\cdot 7^{19} \equiv 7^{19} \pmod{100}.

Now compute $7^{19} \bmod 100$ by repeated squaring:

7^1 = 7,\qquad 7^2 = 49,\qquad 7^4 = 49^2 = 2401 \equiv 1 \pmod{100},

so remarkably $7^4 \equiv 1 \pmod{100}$ already (the true order of $7$ modulo $100$ divides $40$ and in fact equals $4$ — this refinement is the subject of The Order of an Element). Then

19 = 4\cdot 4 + 3 \implies 7^{19} = (7^4)^4 \cdot 7^3 \equiv 1^4 \cdot 343 \equiv 343 \bmod 100 \equiv 43.

So $7^{2019} \equiv 43 \pmod{100}$ . Note that Euler's theorem alone (using the exact exponent $\varphi(100)=40$ ) already gives a correct, finite computation; the fact that the true period is the smaller number $4$ is extra information not supplied by Euler's theorem itself, but consistent with it since $4 \mid 40$ .

Example 2 — a modulus with three distinct prime factors. Compute $17^{500} \bmod 105$ . Factor $105 = 3 \cdot 5 \cdot 7$ . Check $\gcd(17,105)=1$ : $17$ is prime and none of $3,5,7$ divide it, so indeed $\gcd(17,105)=1$ and Euler's theorem applies. Compute $\varphi(105)$ using multiplicativity over the distinct prime factors:

\varphi(105) = \varphi(3)\varphi(5)\varphi(7) = 2 \cdot 4 \cdot 6 = 48.

So $17^{48} \equiv 1 \pmod{105}$ . Reduce the exponent: $500 = 48 \cdot 10 + 20$ , so $500 \equiv 20 \pmod{48}$ , giving

17^{500} \equiv 17^{20} \pmod{105}.

Compute $17^{20} \bmod 105$ by repeated squaring, reducing mod $105$ at every step:

17^1 = 17,

17^2 = 289 = 2\cdot 105 + 79 \equiv 79 \pmod{105},

17^4 \equiv 79^2 = 6241 = 59\cdot 105 + 46 \equiv 46 \pmod{105},

17^8 \equiv 46^2 = 2116 = 20\cdot 105 + 16 \equiv 16 \pmod{105},

17^{16} \equiv 16^2 = 256 = 2\cdot 105 + 46 \equiv 46 \pmod{105}.

Now write $20 = 16 + 4$ , so

17^{20} = 17^{16}\cdot 17^{4} \equiv 46 \cdot 46 = 2116 \equiv 16 \pmod{105}.

So $17^{500} \equiv 16 \pmod{105}$ . As a check via the Chinese Remainder Theorem: modulo $3$ , $17\equiv 2$ , and $\varphi(3)=2$ so $2^{500}=2^{2\cdot250}\equiv 1 \pmod 3$ ; indeed $16 \equiv 1 \pmod 3$ . Modulo $5$ , $17\equiv 2$ , $\varphi(5)=4$ , $500 \equiv 0 \pmod 4$ so $2^{500}\equiv 1\pmod 5$ ; indeed $16\equiv 1\pmod 5$ . Modulo $7$ , $17 \equiv 3$ , $\varphi(7)=6$ , $500 = 6\cdot83+2$ so $3^{500}\equiv 3^2=9\equiv 2\pmod 7$ ; indeed $16 \equiv 2 \pmod 7$ . All three checks agree with $16 \bmod 105$ , confirming the answer.

\gcd(a,n)=1

Scope, edge cases & common traps

Situation	What happens
$n = 1$	$\varphi(1) = 1$ by convention (the empty product / single residue class $0 \equiv$ itself is "coprime" vacuously); every integer $a$ satisfies $a^1 \equiv 1 \pmod 1$ trivially, since everything is $\equiv 0 \equiv$ everything mod $1$ .
$n = p$ prime	Recovers Fermat's Little Theorem exactly, since $\varphi(p) = p-1$ .
$\gcd(a,n) \ne 1$	Theorem simply does not apply; conclusion can fail, as shown above.
Exponent smaller than $\varphi(n)$ also works	Common: the actual smallest exponent $d$ with $a^d \equiv 1 \pmod n$ (the order of $a$ ) always divides $\varphi(n)$ , but can be strictly smaller, as seen with $7^4\equiv 1 \pmod{100}$ despite $\varphi(100)=40$ .
Negative or zero exponent	Euler's theorem is stated for exponent $\varphi(n) \geq 1$ ; extending to negative exponents requires interpreting $a^{-1}$ as the modular inverse, which exists precisely because $\gcd(a,n)=1$ .
Reducing huge exponents in computations	Correct only when the base is coprime to the modulus — reduce the exponent modulo $\varphi(n)$ , not modulo $n$ .

Common trapthe classic error

A frequent mistake is reducing the exponent modulo $n$ instead of modulo $\varphi(n)$ , or applying Euler's theorem without first checking $\gcd(a,n)=1$ . Another subtle error is assuming the converse: that if $a^{k} \equiv 1 \pmod n$ for some $k$ , then necessarily $k \geq \varphi(n)$ or $k = \varphi(n)$ . In fact the true minimal such $k$ (the order of $a$ modulo $n$ ) need only divide $\varphi(n)$ ; it can be a proper divisor, as the computation $7^4 \equiv 1 \pmod{100}$ with $\varphi(100)=40$ demonstrates. Euler's theorem asserts an exponent that works, not the smallest one that works — that finer question belongs to the theory of The Order of an Element.

The mathematician behind it

Origins · 1 minLeonhard Euler and how this was discovered

Leonhard Euler

1707–1783 · Basel, Switzerland; Berlin and St. Petersburg Academies

Leonhard Euler was among the most prolific mathematicians in history, contributing foundational results across analysis, mechanics, graph theory, and number theory. Working largely by correspondence with Christian Goldbach, Euler took up Fermat's scattered, often unproved claims about primes and congruences and turned them into a systematic theory. His 1763 memoir generalized Fermat's Little Theorem to composite moduli by introducing what is now called the totient function, proving the theorem that bears his name using the permutation-of-residues argument reproduced above. Euler continued working prolifically even after losing most of his eyesight later in life, dictating calculations to assistants.

History

- 1640: Pierre de Fermat states, without a surviving proof, the special case for prime moduli — Fermat's Little Theorem.

- 1736: Euler publishes the first known proof of Fermat's Little Theorem.

- 1760: Euler introduces the totient function

\varphi(n)

in the course of generalizing Fermat's result to composite moduli.

- 1763: Euler publishes the full generalization,

a^{\varphi(n)} \equiv 1 \pmod n

for

\gcd(a,n)=1

, now called Euler's theorem.

- 1801: Carl Friedrich Gauss, in Disquisitiones Arithmeticae, systematizes congruence notation and reproves Euler's theorem within a broader theory of residues, cementing its modern form.

Why is Euler's theorem considered a generalization of Fermat's Little Theorem?

Fermat's Little Theorem states that for a prime $p$ and any integer $a$ not divisible by $p$ , $a^{p-1} \equiv 1 \pmod p$ . Euler's theorem replaces the prime modulus $p$ with an arbitrary positive integer $n$ and replaces the exponent $p-1$ with $\varphi(n)$ . When $n=p$ is prime, every integer from $1$ to $p-1$ is coprime to $p$ , so $\varphi(p) = p-1$ exactly, and Euler's statement becomes word-for-word Fermat's statement. Thus Fermat's theorem is the special case of Euler's theorem restricted to prime moduli, and Euler's theorem is the natural extension covering all composite moduli as well, using the totient count instead of $p-1$ .

Does Euler's theorem tell us the smallest exponent that works?

No. Euler's theorem only guarantees that $a^{\varphi(n)} \equiv 1 \pmod n$ for some specific exponent, namely $\varphi(n)$ ; it does not claim this is the smallest such exponent. The smallest positive integer $d$ with $a^{d} \equiv 1 \pmod n$ is called the order of $a$ modulo $n$ , and one can prove $d$ always divides $\varphi(n)$ . Sometimes $d = \varphi(n)$ exactly (then $a$ is called a primitive root), but often $d$ is a proper divisor, as in the example $7^4 \equiv 1 \pmod{100}$ even though $\varphi(100) = 40$ . This finer question is the subject of the theory of the order of an element.

What role does the coprimality condition gcd(a,n) = 1 actually play in the proof?

It guarantees that $a$ has a multiplicative inverse modulo $n$ , via Bézout's identity. This inverse is what makes multiplication by $a$ a bijection (an injective map on a finite set, hence a permutation) on the reduced residue system modulo $n$ . Without this bijectivity, the key step of the proof — that multiplying every element of the reduced residue system by $a$ just rearranges it — collapses, since two different residues could then collide to the same product modulo $n$ . The coprimality condition is not a mere technicality; it is precisely what makes the permutation argument valid.

How is Euler's theorem used in RSA encryption?

RSA chooses two large primes $p, q$ , sets $n = pq$ , and computes $\varphi(n) = (p-1)(q-1)$ . A public encryption exponent $e$ and private decryption exponent $d$ are chosen so that $ed \equiv 1 \pmod{\varphi(n)}$ . For a message $m$ coprime to $n$ , encryption computes $c = m^e \bmod n$ and decryption computes $c^d \bmod n$ . Since $ed = 1 + k\varphi(n)$ for some integer $k$ , Euler's theorem gives $c^d = m^{ed} = m \cdot (m^{\varphi(n)})^{k} \equiv m \cdot 1^{k} = m \pmod n$ , recovering the original message. This is the precise mechanism by which Euler's theorem makes RSA decryption correct.

Can Euler's theorem be extended to messages or bases not coprime to n?

The theorem as stated requires $\gcd(a,n)=1$ and can genuinely fail otherwise, as shown in the counterexample with $a=2$ , $n=6$ . However, a related and more delicate result (sometimes attributed to Euler's successors, refined via the Carmichael function or handled case-by-case using the Chinese Remainder Theorem) shows that for RSA-type moduli $n=pq$ with distinct primes, the congruence $m^{ed}\equiv m \pmod n$ still holds for all integers $m$ , coprime to $n$ or not, provided $ed \equiv 1 \pmod{\operatorname{lcm}(p-1,q-1)}$ . This extension uses Fermat's Little Theorem directly modulo each prime factor rather than Euler's theorem modulo the composite $n$ , and is a separate (though related) argument.

What is the group-theoretic meaning of Euler's theorem?

The integers coprime to $n$ , taken modulo $n$ , form a finite group under multiplication, called the group of units $(\mathbb{Z}/n\mathbb{Z})^{\times}$ , with exactly $\varphi(n)$ elements. A basic fact in finite group theory, Lagrange's theorem, states that the order of any element of a finite group divides the order of the group itself. Applying this to the group of units immediately gives that the order of $a$ (the smallest $d$ with $a^d\equiv 1$ ) divides $\varphi(n)$ , and in particular $a^{\varphi(n)} \equiv 1 \pmod n$ . Euler's theorem can thus be seen as the number-theoretic incarnation of this purely algebraic fact, discovered decades before group theory itself was formalized.

Why does the proof fail to be circular, and what exactly does it assume?

The proof assumes only prior facts about reduced residue systems (their existence and size $\varphi(n)$ , from Reduced Residue Systems and the Totient Function), basic properties of congruences (that they respect multiplication), and Bézout's identity from elementary divisibility theory. None of these facts depend on Euler's theorem itself, nor on Fermat's Little Theorem, which is instead derived as a corollary afterward. This ordering — building from more elementary, independently established facts up to the theorem — is what makes the proof logically sound and non-circular.