Euler’s Theorem Explained — Number Theory, Graph Theory, and Applications
What happens when you raise a number to an impossibly large power and then ask: what is the remainder? It sounds like a question designed to break arithmetic, a challenge so absurd that brute computation would take lifetimes. Yet in 1763, Leonhard Euler published a single elegant statement that collapses that impossibility into a few strokes of the pen. Euler’s theorem tells us that if you take any integer \( a \) coprime to a positive integer \( n \), then raising \( a \) to a specific power determined entirely by \( n \) always yields a remainder of one when divided by \( n \). Always. No exceptions. No matter how large the numbers become.
This is not a computational trick. It is a structural fact about the integers themselves, a hidden periodicity woven into modular arithmetic. It quietly underpins the security of every encrypted message you have sent, every online banking transaction you have completed. And it began with a blind man in Saint Petersburg, scribbling formulas he could no longer see.
The Blind Geometer of Saint Petersburg
By the time Leonhard Euler generalized Pierre de Fermat’s little theorem into what we now call the euler theorem in its full glory, he had already lost sight in his right eye. Within a decade, he lost the left as well. None of this slowed him. If anything, blindness seemed to sharpen the architecture of his inner vision. His assistants later described him dictating entire treatises from memory, holding vast chains of algebraic reasoning in his mind like a chess grandmaster holds a board.
Euler arrived at his generalization not in a single flash but through years of patient correspondence and calculation. Fermat had observed more than a century earlier that for any prime \( p \) and any integer \( a \) not divisible by \( p \), the quantity \( a^{p-1} \) leaves a remainder of 1 when divided by \( p \). Fermat, characteristically, offered no proof — only a brief mention in a letter to Frénicle de Bessy in 1640, asserting the result without demonstration. Euler, characteristically, did the actual work. He first proved Fermat’s claim rigorously in 1736, then asked the question that transforms a good theorem into a great one: what if \( n \) is not prime?
This question consumed Euler across decades of work at the Saint Petersburg Academy and later at the Berlin Academy under Frederick the Great. He realized that the exponent \( p – 1 \) in Fermat’s little theorem was not arbitrary. It counted the number of integers less than \( p \) that share no common factor with \( p \). For a prime, that count is simply \( p – 1 \). But for a composite number, the count changes. Euler needed a function to capture it, so he invented one — a function that would eventually bear his name and reshape number theory.
What Euler’s Theorem Actually Says, Before the Symbols
Imagine a clock. Not an ordinary twelve-hour clock, but one with \( n \) positions numbered from 0 to \( n – 1 \). Every time you multiply the current position by some fixed number \( a \), the hand jumps to a new position, landing wherever the remainder falls after division by \( n \). This is modular arithmetic, and it is the world in which the euler fermat theorem lives.
Now here is the remarkable claim. If \( a \) and \( n \) share no common factor — if they are, in number theory terms, coprime — then there exists a specific number of jumps after which the hand always returns to position 1. Not approximately. Not usually. Always. That number of jumps is precisely \( \phi(n) \), the count of integers between 1 and \( n \) that are coprime to \( n \). This counting function is Euler’s totient function, sometimes called the euler phi function, and it is the heartbeat of the theorem.
Think of it this way. You are in a room with \( n \) doors, but only \( \phi(n) \) are unlocked — those corresponding to numbers sharing no factor with \( n \). If you walk through exactly \( \phi(n) \) unlocked doors in sequence, multiplying your position at each step by \( a \), you will find yourself back where you started, standing at position 1. The cycle is guaranteed, and its length divides \( \phi(n) \) exactly.
This is the conceptual core of number theory Euler scholars have studied for centuries: the integers modulo \( n \) harbor a hidden rotational symmetry, and the Euler-Fermat connection reveals its precise period. Before we write a single formula, we should feel the weight of this: multiplication by a coprime number, repeated enough times in a modular world, always brings you home.
From Intuition to Rigor — Euler’s Theorem Proof
Now let us follow Euler’s own reasoning and see how the proof assembles itself from elementary parts. The statement of Euler’s theorem is compact and beautiful: if \( \gcd(a, n) = 1 \), then
where \( \phi(n) \) is Euler’s totient function, counting the number of integers from 1 to \( n \) that are coprime to \( n \). To prove this, we need to understand what happens when we multiply all those coprime residues by \( a \) simultaneously.
The Reduced Residue System
Let the integers coprime to \( n \) and lying between 1 and \( n \) be denoted \( r_1, r_2, \ldots, r_{\phi(n)} \). This set forms what algebraists call a reduced residue system modulo \( n \). For instance, when \( n = 10 \), the coprime residues are 1, 3, 7, and 9, so \( \phi(10) = 4 \). Now consider multiplying every element in this set by \( a \), where \( \gcd(a, n) = 1 \). The products \( ar_1, ar_2, \ldots, ar_{\phi(n)} \) form, modulo \( n \), a permutation of the original set. This is the crux — and it requires two observations.
First, each product \( ar_i \) is itself coprime to \( n \), because the product of two numbers each coprime to \( n \) is also coprime to \( n \). Second, no two products are congruent modulo \( n \): if \( ar_i \equiv ar_j \pmod{n} \), then since \( \gcd(a, n) = 1 \), we can cancel \( a \) to get \( r_i \equiv r_j \pmod{n} \), which is impossible when \( i \neq j \). So the set \( \{ar_1 \bmod n, \, ar_2 \bmod n, \, \ldots, \, ar_{\phi(n)} \bmod n\} \) is exactly the original set \( \{r_1, r_2, \ldots, r_{\phi(n)}\} \), just reordered.
The Cancellation
Since these two sets are identical modulo \( n \), their products must be congruent: \( (ar_1)(ar_2)\cdots(ar_{\phi(n)}) \equiv r_1 r_2 \cdots r_{\phi(n)} \pmod{n} \). Factoring out gives \( a^{\phi(n)} \cdot (r_1 r_2 \cdots r_{\phi(n)}) \equiv r_1 r_2 \cdots r_{\phi(n)} \pmod{n} \). Now the product \( r_1 r_2 \cdots r_{\phi(n)} \) is itself coprime to \( n \), since every factor is. We may therefore cancel it, yielding \( a^{\phi(n)} \equiv 1 \pmod{n} \), which completes the euler’s theorem proof.
Notice how naturally this argument extends Fermat’s original insight. When \( n = p \) is prime, the coprime residues are simply \( 1, 2, \ldots, p-1 \), so \( \phi(p) = p – 1 \), and the theorem reduces to \( a^{p-1} \equiv 1 \pmod{p} \) — which is exactly Fermat’s little theorem. The euler fermat relationship is not an analogy; it is a logical containment. Euler did not merely generalize Fermat; he revealed that Fermat’s result was a single chapter in a far larger story about the multiplicative structure of the integers.
The Epistemological Turn — What Does This Theorem Know About Reality?
Here is what should genuinely unsettle us: Euler’s theorem is not about any particular numbers. It is about all of them, simultaneously, forever. It makes an infinite claim — that for every coprime pair \( (a, n) \), the congruence \( a^{\phi(n)} \equiv 1 \pmod{n} \) holds — verified not by testing cases but by pure reasoning. No experiment was conducted. No data was collected. And yet this theorem now secures the RSA cryptosystem, which protects real financial transactions, real military communications, real human secrets. What does it mean that an abstract truth, born in the mind of an eighteenth-century blind man, can reach forward through centuries to govern the behavior of silicon chips?
The first question worth confronting honestly is whether Euler discovered this theorem or invented it. The Platonist answer — the position held, in various forms, by Gödel and by most working number theorists who pause to reflect on the matter — is that the multiplicative structure of the integers exists independently of any human mind, and that Euler simply perceived a feature of that structure the way a cartographer perceives a mountain range. On this view, even if Euler had never been born, the coprime residues modulo \( n \) would still form a group under multiplication, and the order of that group would still divide \( \phi(n) \). The theorem would be true; it would merely be unknown.
The most defensible reading, I believe, is that this Platonist position is not just a philosophical preference but an almost unavoidable conclusion forced by the theorem’s own character. Consider the alternative: if Euler’s theorem were merely a human invention, a game played with symbols we made up, then its effectiveness in cryptography would be a staggering coincidence. The RSA algorithm works — not approximately, not statistically, but with the absolute certainty of a logical tautology — precisely because the theorem captures something that was already true about the integers before anyone thought to ask. Imre Lakatos, in his Proofs and Refutations, argued that mathematical knowledge grows through a quasi-empirical process of conjecture, proof, and counterexample, and that even “proven” theorems are subject to revision as concepts are refined. But Euler’s theorem resists this narrative. Its proof has not been revised since the eighteenth century — only re-expressed in the language of group theory, which, far from challenging its validity, revealed it as a special case of Lagrange’s theorem on the orders of subgroups. Each reformulation has made the theorem look more inevitable, not less.
The second question cuts deeper: how do we know the proof is correct? We followed a finite chain of deductive steps, each checkable, each apparently airtight. But Wittgenstein raised a disquieting point in his Remarks on the Foundations of Mathematics: following a rule — even a logical rule — requires interpretation at every step, and we can never fully escape the circularity of using reason to validate reason. If a flaw were found in Euler’s proof tomorrow — not a mere gap but a genuine logical error — the consequences would cascade through modern cryptography and abstract algebra alike. And yet this possibility, however remote, is not zero. What gives us confidence is not certainty but something more human and more interesting: the proof has been read, taught, re-derived, and applied by thousands of independent minds across three centuries, each one testing the chain link by link. Mathematical truth, in practice, is a social achievement as much as a logical one — a consensus forged in the fire of relentless scrutiny. This does not make it fragile. It makes it the most robust kind of knowledge we possess.
The Historical Debate — From Fermat’s Margins to Euler’s Mastery
The path from Fermat to Euler was anything but smooth. Fermat stated his little theorem in a letter to Frénicle de Bessy in 1640, but as with so many of Fermat’s claims, the proof was absent. For nearly a century, the result lingered in a peculiar epistemic limbo — believed to be true, used in calculations, but never rigorously established. Leibniz attempted a proof and may have succeeded, though his notes remain ambiguous. It was Euler who, in a 1736 paper presented to the Saint Petersburg Academy, finally nailed the proof down — and then, restlessly, began asking what lay beyond.
The generalization to composite moduli did not come easily. Euler introduced what he called the “totient” in stages, first computing specific values — \( \phi(12) = 4 \), \( \phi(15) = 8 \) — before arriving at the general multiplicative formula for computing \( \phi(n) \) from the prime factorization of \( n \). Even among his contemporaries, the significance was not immediately clear. Gauss, writing decades later in the Disquisitiones Arithmeticae (1801), reformulated much of Euler’s work in the language of congruences, giving it the modern notation and framework we use today. Gauss acknowledged Euler’s priority but quietly improved the proofs, sharpening arguments that Euler had sometimes left in a rougher state. The primary source material on Euler’s theorem reveals a result that was not born perfect — it was argued into clarity across generations of mathematicians, each adding rigor to Euler’s original vision.
The debate was not about whether the theorem was true. It was about what it meant — whether it was a curiosity about remainders or a window into the deep algebraic structure of the integers. History answered that question decisively.
Legacy and Connections — From Pure Abstraction to Digital Security
The reach of Euler’s theorem today is extraordinary. In the twentieth century, the theorem became the mathematical engine of RSA encryption, invented by Rivest, Shamir, and Adleman in 1977. The RSA algorithm exploits the fact that computing \( \phi(n) \) is easy when you know the prime factors of \( n \) — and effectively impossible when you do not. Every time you see a padlock icon in your browser’s address bar, Euler’s three-century-old insight is working silently beneath the surface.
In pure mathematics, the theorem catalyzed the development of group theory. The reduced residue classes modulo \( n \) form a group under multiplication, and Euler’s theorem is a direct consequence of Lagrange’s theorem applied to this group. The Euler phi function itself became a central object of study in analytic number theory, appearing in the distribution of primes, in the theory of cyclotomic polynomials, and in the computation of Ramanujan sums. In combinatorics, it counts the number of generators of cyclic groups. In computer science, fast modular exponentiation — the practical implementation of Euler’s theorem — is among the most widely used algorithms on Earth.
What Euler set in motion was not merely a theorem but a way of thinking: that the integers, far from being a featureless sequence, possess an internal architecture rich enough to organize vast swaths of modern technology and abstract thought.
The Open Question
Euler’s theorem tells us that exponentiation in modular arithmetic is periodic — that powers of a coprime base cycle back to 1 with a period dividing \( \phi(n) \). But why? Not why in the sense of proof — we have the proof. Why in the sense of explanation. Why should the integers care about cycling? Why should multiplication, iterated long enough in a finite system, return to its origin like a planet completing an orbit?
We have named this phenomenon. We have proved it. We have built civilizations of encrypted data on top of it. But naming a thing is not the same as understanding it. The deepest question Euler’s theorem leaves us is not mathematical at all — it is the question of why the universe is built from structures that obey patterns we can describe but may never fully comprehend.
What is Euler’s theorem in simple terms?
Euler’s theorem states that if two positive integers \( a \) and \( n \) share no common factor, then \( a \) raised to the power \( \phi(n) \) — where \( \phi(n) \) counts integers less than \( n \) that are coprime to \( n \) — leaves a remainder of 1 when divided by \( n \). It generalizes Fermat’s little theorem from primes to all positive integers.
References and Further Reading
Hardy, G. H. and Wright, E. M., An Introduction to the Theory of Numbers, 6th edition, Oxford University Press, 2008.
Brilliant.org, “Euler’s Theorem,” https://brilliant.org/wiki/eulers-theorem/.
Art of Problem Solving, “Euler’s Totient Theorem,” artofproblemsolving.com.
Lakatos, Imre, Proofs and Refutations: The Logic of Mathematical Discovery, Cambridge University Press, 1976.
Wittgenstein, Ludwig, Remarks on the Foundations of Mathematics, revised edition, MIT Press, 1983.
