Euler’s Phi Function

students, imagine trying to count how many numbers “work well” with a chosen number. For example, if you pick $10$, which numbers from $1$ to $10$ share no common factor with $10$ except $1$? This counting idea leads to one of the most important functions in number theory: Euler’s phi function, written as $\varphi(n)$. It is a key idea in the topic of Fermat and Euler because it helps explain Euler’s theorem and connects closely to Fermat’s Little Theorem. 📘

Introduction to Euler’s Phi Function

Euler’s phi function $\varphi(n)$ counts the positive integers from $1$ to $n$ that are coprime to $n$. Two numbers are coprime if their greatest common divisor is $1$. In symbols, $\gcd(a,n)=1$ means $a$ and $n$ share no common factor bigger than $1$.

For example, when $n=10$, the numbers from $1$ to $10$ are $1,2,3,4,5,6,7,8,9,10$. The ones coprime to $10$ are $1,3,7,9$, so $$\varphi(10$)=4.

This function helps measure how many numbers are “compatible” with $n$ in modular arithmetic. That makes it useful in cryptography, divisibility patterns, and proofs involving powers of numbers.

What you should learn in this lesson

What $\varphi(n)$ means and how to interpret it.
How to calculate $\varphi(n)$ for common values.
How prime factors help us find $\varphi(n)$ efficiently.
How $\varphi(n)$ connects to Euler’s theorem and Fermat’s Little Theorem.

Understanding Coprime Numbers and Counting

Let’s start with the idea of being coprime. If a number shares no prime factors with $n$, then it is counted by $\varphi(n)$.

Take $n=8$. The numbers from $1$ to $8$ are $1,2,3,4,5,6,7,8$. The numbers coprime to $8$ are $1,3,5,7$, because each has $\gcd$ equal to $1$ with $8$. So $$\varphi(8$)=4.

Now take $n=9$. The numbers from $1$ to $9$ that are coprime to $9$ are $1,2,4,5,7,8$. So $$\varphi(9$)=6.

A helpful way to think about $\varphi(n)$ is this: it counts the “units” modulo $n$. A number $a$ is a unit modulo $n$ if it has a multiplicative inverse modulo $n$, which happens exactly when $\gcd(a,n)=1$.

That is why $\varphi(n)$ matters in modular arithmetic. It tells us how many numbers can act like reversible elements under multiplication mod $n$. 🔁

Finding $\varphi(n)$ for Prime Numbers and Prime Powers

The easiest case is when $n$ is prime. If $p$ is prime, then every number from $1$ to $p-1$ is coprime to $p$. The only number not counted is $p$ itself, because $\gcd(p,p)=p$.

So for a prime $p$,

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

Example: if $p=7$, then $\varphi(7)=6$.

Now consider a power of a prime, such as $p^k$. The formula is

$$\varphi(p^k)=p^k-p^{k-1}.$$

Why? Because the numbers not coprime to $p^k$ are exactly those divisible by $p$. Among $1,2,\dots,p^k$, there are $p^{k-1}$ multiples of $p$. So we subtract those from the total.

Example: for $8=2^3$,

$$\varphi(8)=2^3-2^2=8-4=4,$$

which matches the list $1,3,5,7.

Example: for $27=3^3$,

$$\varphi(27)=3^3-3^2=27-9=18.$$

This prime power formula is one of the most useful tools for calculating $\varphi(n)$.

The Multiplicative Formula for General $n$

Most numbers are not prime powers, so we need a general method. If the prime factorization of $n$ is

$$n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r},$$

then Euler’s phi function is

$$\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_r}\right).$$

This works because each factor $\left(1-\frac{1}{p_i}\right)$ removes the numbers divisible by that prime factor.

Let’s do a real example with $n=12$.

First factorize:

$$12=2^2\cdot 3.$$

Then apply the formula:

$$\varphi(12)=12\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right).$$

Compute step by step:

$$\varphi(12)=12\cdot \frac{1}{2}\cdot \frac{2}{3}=4.$$

The numbers coprime to $12$ are $1,5,7,11, so the answer checks out.

Another example: $n=20$.

$$20=2^2\cdot 5.$$

Then

$$\varphi(20)=20\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=20\cdot \frac{1}{2}\cdot \frac{4}{5}=8.$$

The coprime numbers are $1,3,7,9,11,13,17,19.

This formula is powerful because it turns a counting problem into a prime factorization problem. 🧠

Why Euler’s Phi Function Matters in Fermat and Euler

Euler’s phi function is not just a counting tool. It is the key ingredient in Euler’s theorem.

Euler’s theorem says that if $\gcd(a,n)=1$, then

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

This means that when $a$ and $n$ are coprime, raising $a$ to the power $\varphi(n)$ gives a remainder of $1$ when divided by $n$.

For example, with $n=10$ and $a=3$, we know $\gcd(3,10)=1$ and $\varphi(10)=4$. So Euler’s theorem predicts

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

Check it:

$$3^4=81,$$

and $81$ leaves remainder $1$ when divided by $10$. ✅

This theorem generalizes Fermat’s Little Theorem. If $p$ is prime, then $\varphi(p)=p-1$, so Euler’s theorem becomes

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

when $\gcd(a,p)=1$.

That is exactly Fermat’s Little Theorem.

So $\varphi(n)$ is the bridge between counting and modular exponentiation. It tells us the exponent that makes the theorem work.

Using $\varphi(n)$ in Practice

Let’s see how to apply $\varphi(n)$ in a practical way.

Suppose you want to find $\varphi(36)$.

First write the factorization:

$$36=2^2\cdot 3^2.$$

Then use the product formula:

$$\varphi(36)=36\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=36\cdot \frac{1}{2}\cdot \frac{2}{3}=12.$$

So there are $12$ numbers from $1$ to $36$ that are coprime to $36$.

You can also use $\varphi(n)$ to simplify powers modulo $n$. For example, to compute $2^{100} \pmod{9}$, first note that $\gcd(2,9)=1$ and $\varphi(9)=6$. So

$$2^6\equiv 1 \pmod 9.$$

Now write $100=6\cdot 16+4$, so

$$2^{100}=\left(2^6\right)^{16}2^4\equiv 1^{16}\cdot 2^4 \equiv 16 \equiv 7 \pmod 9.$$

This kind of reasoning is very useful because it reduces huge exponents into manageable calculations.

Common Mistakes and Important Details

A few details matter a lot when working with $\varphi(n)$:

$\varphi(n)$ counts numbers from $1$ to $n$, not from $0$ to $n$.
The number $n$ itself is counted only if it is coprime to itself, which happens only when $n=1$.
Being odd does not always mean coprime. For example, $9$ and $15$ are both odd, but $\gcd(9,15)=3$.
The formula $\varphi(n)=n\prod\left(1-\frac{1}{p}\right)$ uses the distinct prime factors of $n$, not the exponents.

As a quick check, for any prime $p$, the value must be $p-1$. For a number like $n=1$, we have only one number, and it is coprime to $1$, so

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

This is a special case worth remembering.

Conclusion

Euler’s phi function $\varphi(n)$ counts how many integers from $1$ to $n$ are coprime to $n$. It starts with a simple idea—counting numbers with $\gcd(a,n)=1$—but it becomes a major tool in number theory. You can calculate it for primes, prime powers, and general numbers using prime factorization. Most importantly, it connects directly to Euler’s theorem,

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

and helps explain the structure behind Fermat’s Little Theorem.

students, when you understand $\varphi(n)$, you understand one of the main counting ideas that powers the whole Fermat and Euler topic. It is a small-looking function with big mathematical impact. 🌟

Study Notes

Euler’s phi function $\varphi(n)$ counts the integers from $1$ to $n$ that are coprime to $n$.
Two numbers are coprime if their greatest common divisor is $1$.
For a prime $p$, $$\varphi(p)=p-1.$$
For a prime power $p^k$, $$\varphi(p^k)=p^k-p^{k-1}.$$
For $n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$,

$$\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_r}\right).$$

Euler’s theorem says that if $\gcd(a,n)=1$, then $$a^{\varphi(n)}\equiv 1 \pmod n.$$
Fermat’s Little Theorem is a special case of Euler’s theorem when $n$ is prime.
$\varphi(n)$ is important because it counts the number of invertible elements modulo $n$.
Prime factorization is the main tool for finding $\varphi(n)$ efficiently.
Common values: $\varphi(1)=1,$ $\varphi(10)=4,$ $\varphi(12)=4,$ $$\varphi(36)=12.$$