Euler’s Theorem: proof by modular arithmetic

In my last post I explained the first proof of Fermat’s Little Theorem: in short, $a \cdot 2a \cdot 3a \cdot \dots \cdot (p-1)a \equiv (p-1)! \pmod p$ and hence $a^{p-1} \equiv 1 \pmod p$ . Today I want to show how to generalize this to prove Euler’s Totient Theorem, which is itself a generalization of Fermat’s Little Theorem:

If $n \geq 1$ and $a$ is any integer relatively prime to $n$ , then $a^{\varphi(n)} \equiv 1 \pmod n$ .

Remember that $\varphi(n)$ is the function that tells us how many positive integers less than $n$ are relatively prime to (share no common factors with) $n$ . So, for example, suppose $n = 12$ and $a = 7$ . There are four positive integers among $\{1, \dots, 11\}$ which are relatively prime to $12$ (namely, $1$ , $5$ , $7$ , and $11$ ), so the theorem says we should have $7^4 \equiv 1 \pmod{12}$ , which we can verify: $7^4 = 2401 = 200 \cdot 12 + 1$ .

Once again, we start by considering the set of multiples of $a$ up to $(n-1)a$ :

$\{a, 2a, 3a, \dots, (n-1)a \}$ .

However, in this more general context we don’t want to use all of them! Our proof of Fermat’s Little Theorem relied on the fact that if $p$ (here, $n$ ) is prime, then none of $1, 2, \dots, (p-1)$ have any factors in common with it. But if $n$ is not prime that may no longer be true. So, instead of the set above, we will look at the set of multiples of $a$ which are relatively prime to $n$ . Since we already assumed $a$ is relatively prime to $n$ , this is equivalent to saying we want multiples $ka$ where $k$ is relatively prime to $n$ :

$M = \{ ka \mid 1 \leq k < n, \gcd(k,n) = 1 \}$

( $\gcd(k,n) = 1$ is another way to say that $k$ and $n$ are relatively prime: they share no factors in common if and only if they have no nontrivial common divisor, that is, their greatest common divisor is $1$ .) Note that $|M| = \varphi(n)$ : the number of things relatively prime to $n$ between $1$ and $n-1$ is exactly what $\varphi(n)$ counts.

As an example, suppose $n = 12$ and $a = 5$ . The only multiples of $a$ which are relatively prime to $n$ are

$\{1 \cdot 5, 5 \cdot 5, 7 \cdot 5, 11 \cdot 5\} = \{5, 25, 35, 55\}.$

If we take these $\pmod {12}$ , we get

$\{5, 1, 11, 7\}$

and hey, look at that—it’s the numbers relatively prime to $12$ again, just in a different order! As another example, suppose $n = 20$ and $a = 3$ . The numbers relatively prime to $20$ are $\{1,3,7,9,11,13,17,19\}$ , and we can check that

$\{3,9,21,27,33,39,51,57\} \equiv \{3,9,1,7,13,19,11,17\} \pmod {20}.$

So the claim is that if we start with all the numbers relatively prime to $n$ , multiply them all by $a$ , and then take their remainders $\pmod n$ , we get back the same set we started with (though quite possibly in a different order). More formally, let $\Phi(n) = \{ k \mid 1 \leq k < n, \gcd(k,n) = 1 \}$ be the set of numbers relatively prime to $n$ . Then the claim is that

$a \cdot \Phi(n) \equiv \Phi(n) \pmod{n}$

where multiplying a number by a set, like $a \cdot \Phi(n)$ , means to multiply each element of the set by the given number.

The proof of this claim starts out quite similar to the proof from last time. First, suppose there are two multiples of $a$ , say, $ja$ and $ka$ , which have the same remainder when divided by $n$ . We can write this as $ja \equiv ka \pmod n$ . Subtracting $ka$ from both sides and factoring out $a$ , we find that $a(j-k) \equiv 0 \pmod n$ , that is, $a(j-k)$ is divisible by $n$ . By assumption, $a$ is relatively prime to $n$ , so the only way for this to be true is if $j - k$ is divisible by $n$ , but since $j$ and $k$ are less than $n$ , the only way for this to happen is if $j - k = 0$ , that is, $j = k$ . So this means that if we start with different multiples of $a$ , we get different remainders out.

However, this isn’t enough—this time we actually care about which remainders we get. We have to prove that if we start with only those multiples which are relatively prime to $n$ , we get exactly the same remainders out. So far, we haven’t used the fact that $j$ and $k$ are relatively prime to $n$ at all. Indeed, if we take all multiples of $a$ , we still end up with each remainder only once:

$\{5,10,15,20,25,30,35,40,45,50,55\} \pmod {12} = \{5,10,3,8,1,6,11,4,9,2,7\}$

However, you’ll see later why we specifically want only the remainders which are relatively prime to $n$ .

So, assuming $j$ is relatively prime to $n$ , consider the remainder $r$ we get after dividing $ja$ by $n$ . So, $ja$ is $r$ more than some multiple of $n$ , that is, $ja = qn + r$ . We want to show that $r$ is relatively prime to $n$ . If $r$ had a factor $d$ in common with $n$ , then the whole right-hand side $qn + r$ would be divisible by $d$ (because a sum of multiples of $d$ is also a multiple of $d$ ). But then the left-hand side, $ja$ , would be divisible by $d$ also, but neither $j$ nor $a$ can be divisible by $d$ , since both are relatively prime to $n$ . Hence $r$ in fact has no factors in common with $n$ .

We’re almost done now. We start with the equation

$a \cdot \Phi(n) \equiv \Phi(n) \pmod n$

and, just like last time, we now multiply together everything on the left and everything on the right. On the left we can factor out $\varphi(n)$ copies of $a$ , and this leaves us with

$\displaystyle a^{\varphi(n)} \prod \Phi(n) \equiv \prod \Phi(n) \pmod n$

where $\prod$ means to take the product of all the elements in a set. Finally, we can see why it was important that we only took multiples of $a$ which are relatively prime to $n$ : this means the product $\prod \Phi(n)$ shares no common factors with $n$ , which means we can divide by it on both sides, concluding that

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

If we had instead used the multiples of $a$ as before, we would end up with

$a^{n-1} (n-1)! \equiv (n-1)! \pmod n,$

which is a valid equation, but the problem is we are stuck here: dividing both sides by $(n-1)!$ would not result in a valid modular equation, since $(n-1)!$ shares one or more common factors with $n$ when $n$ is not prime.

Euler’s Theorem: proof by modular arithmetic

About Brent

Follow Blog via Email

Meta

Categories

Archives

Euler’s Theorem: proof by modular arithmetic

Share this:

Like this:

Related

About Brent

Follow Blog via Email

Meta

Categories

Archives