Euler’s Totient Theorem

In honour of Leonhard Euler’s 306th birthday (and also to celebrate my finally having figured out how to use Mathjax on my blog^[1]) I thought I’d have a quick look at one of his great accomplishments. This result is sometimes known simply as Euler’s theorem… but that really is a hopelessly ambiguous name.

The result revolves around a single, simple idea: that of the totient. This starts with the observation that any two whole numbers either have a factor in common, or they don’t. For instance 12 and 33 share a a factor of 3, while 8 and 9 have only 1 in common (which we don’t count, since it’s a factor of everything). That is to say, 8 and 9 are coprime.

The totient of some number $n$ , written $\phi(n)$ , is the the number of numbers between 1 and $n$ which are coprime to it. For instance, the totient of 8 is 4, since 1, 3, 5, 7 are coprime to it (while 2, 4, 6, 8 aren’t). So we can say that $\phi(8)=4$ .

Calculating the totient function seems to require a lot of counting. What is $\phi(100)$ , for instance? It looks nastily as if we will have to traipse through the numbers 1 to 99 in turn, laboriously determining which is coprime to 100 and which isn’t.

Euler’s first theorem about the totient theorem is that there is a much quicker way, a formula. It works like this: say $p_1, p_2, \ldots$ are the prime numbers dividing $n$ . Then $\phi(n)= n \times \left(1 - \frac{1}{p_1} \right) \times \left(1 - \frac{1}{p_2} \right) \times \ldots$ .
In the case of 100, the relevant prime numbers are 2 and 5, so we can calculate the answer very quickly: $\phi(100)=100 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{5})=40$ .

Now, if we start with a prime number $p$ , then $\phi(p)=p-1$ ). How so? Well, no number between 1 and $p-1$ can share a factor with $p$ , since the only possible factors are 1 (which doesn’t count for present purposes) and $p$ itself, which is too big. For instance, all of 1,2,3,4,5,6 are coprime to 7, and so $\phi(7)=6$ .

Euler’s insight, then, was that the totient function might allow certain facts about prime numbers $p$ to be extended to any numbers $n$ , by judiciously replacing occurrences of $p-1$ with $\phi(n)$ . The context where he applied this idea was…

Fermat’s Little Theorem

In 1640, Pierre de Fermat had made the following observation about prime numbers: if $p$ is prime (e.g. $p=3$ ), and $a$ is any whole number not divisible by $p$ (e.g. $7$ ), then $a^{p-1}$ always leaves a remainder of 1, when divided by $p$ (in this case $7^{3-1} = 49 = 3 \times 16+1$ . We write this as $a^{p-1} \equiv 1 \textrm{ mod } p$ .

Fermat’s Little Theorem is a delightful result. It has also turned out to be amazingly useful and important, serving as the lynchpin of the public key cryptography on which we modern day internet users all rely. But Fermat – somewhat characteristically – never provided a proof. That had to wait for the later thinkers Gottfried Leibniz and Leonhard Euler. Euler not only proved Fermat’s little theorem, he extended it. Euler’s theorem says this: if $n$ is any number and $a$ is any number coprime to $n$ , then $a^{\phi(n)} \equiv 1 \textrm{ mod } n$ .

For instance, taking $n=8$ and $a=3$ (and remembering that $\phi(8)=4)$ it is true that $3^4=81=8 times 10+1$ .

This elegant, unexpected theorem has perhaps been rather eclipsed by Euler’s other magnificent achievements. I’ll end with a couple of open problems about the totient function:

Robert Carmichael asked: is there some number $m$ , where there is exactly one number (n) with $\phi(n)=m$ ? (If we replace ‘exactly one’ with ‘exactly two’ or ‘exactly three’, etc., the answer is yes!)

We know that $\phi(p)=p-1$ for any prime number $p$ , and it is fairly easy to see that this can only hold if $p$ is prime. A weaker condition is that $\phi(n)$ should divide $n-1$ . Derrick Lehmer asked whether there is any non-prime number which satisfies this. None is known so far!

[1] Update: since my last blog reboot, I am no longer using MathJax,but the WordPress.com Latex support.

4 responses to “Euler’s Totient Theorem”

rdm

April 15, 2013 at 5:48 pm

?(1) is 1, since 1 has no prime factors. And, of course 1 divides 0 evenly (with no remainder).

Looking to Euler | nebusresearch

April 15, 2013 at 6:46 pm

[…] while is true, which is embarrassing and hard to do — but in the meanwhile I’d like to remember Leonhard Euler’s 306th birthday and point to Richard Elwes’s essay here about Euler’s totient function. “Totient” is, as best I can determine, a word […]

Carnival of Mathematics 98 | andrewt.net

May 8, 2013 at 12:25 pm

[…] Richard Elwes has blogged about totients, handily explaining what “nontotients” are for anyone who obediently didn’t Google them earlier. The formula for finding them quickly is neat — and sort of obvious in retrospect so maybe try to find it before he tells you. […]

Euler’s Partition Theorem | Simple City

June 17, 2015 at 4:15 pm

[…] Theorem. Not that one. No, not the one on this commemorative stamp either. No, no, not the totient function one. (Good guess […]

Euler’s Totient Theorem

Fermat’s Little Theorem

Share this:

4 responses to “Euler’s Totient Theorem”

Leave a comment Cancel reply