[Introduction to Number Theory Series Part 17] How Do Euler's Totient Function and Euler's Theorem Extend Fermat's Little Theorem?

Fermat's little theorem is powerful, but it only works directly with prime moduli. To understand powers modulo composite numbers, we need Euler's totient function and Euler's theorem.

What this post covers

• What Euler's totient function counts
• The statement of Euler's theorem
• Why Fermat's theorem is a special case
• A few examples with composite moduli

Key terms

• Euler's totient function: the number of integers from 1 to n that are coprime to n
• Euler's theorem: if gcd(a,n)=1, then a^{\varphi(n)} \equiv 1 \pmod n
• coprime: having gcd 1
• Fermat's little theorem: the prime-modulus special case

What does \varphi(n) count?

The value \varphi(n) counts the natural numbers from 1 to n that are coprime to n.

For example, when n=8, the numbers coprime to 8 are

$$1,3,5,7,$$

so

$$\varphi(8)=4.$$

Likewise, for n=10, the coprime numbers are 1,3,7,9, so

$$\varphi(10)=4.$$

This function also measures how many residue classes modulo n can have inverses.

Euler's theorem

If gcd(a,n)=1, then

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

That is Euler's theorem.

Why does this extend Fermat's theorem?

If p is prime, then every number from 1 to p-1 is coprime to p, so

$$\varphi(p)=p-1.$$

Substituting into Euler's theorem gives

$$a^{p-1}\equiv 1 \pmod p,$$

which is exactly Fermat's little theorem.

Example 1: 3^{100} \pmod {10}

Since

$$\varphi(10)=4$$

and gcd(3,10)=1, we get

$$3^4 \equiv 1 \pmod {10}.$$

So

$$3^{100} = (3^4)^{25} \equiv 1^{25} \equiv 1 \pmod {10}.$$

Example 2: 5^{20} \pmod 8

Since \varphi(8)=4 and gcd(5,8)=1,

$$5^4 \equiv 1 \pmod 8.$$

So

$$5^{20}=(5^4)^5 \equiv 1^5 \equiv 1 \pmod 8.$$

Common mistakes

1. Thinking \varphi(n)=n-1 for every n

That is true only when n is prime.

2. Forgetting the coprime condition

Euler's theorem requires gcd(a,n)=1.

3. Memorizing Fermat and Euler as unrelated theorems

Fermat's theorem is the prime-modulus special case of Euler's theorem.

Wrap-up

Euler's totient function counts coprime numbers, and Euler's theorem uses that count to control powers modulo a general modulus.

Next we step back and place this and similar quantities into the broader framework of arithmetic functions.