# Euler Totient Function

## Counting Coprime Residues

Euler's totient function is an arithmetic function denoted by

$$
\varphi(n).
$$

For a positive integer $n$, it counts the integers $a$ satisfying

$$
1\le a\le n
$$

and

$$
\gcd(a,n)=1.
$$

Thus

$$
\varphi(n)=\#\{a:1\le a\le n,\ \gcd(a,n)=1\}.
$$

For example, the integers from $1$ to $10$ that are coprime to $10$ are

$$
1,3,7,9.
$$

Therefore

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

The totient function measures how many residue classes modulo $n$ are invertible.

## Prime Moduli

If $p$ is prime, then every integer

$$
1,2,\ldots,p-1
$$

is coprime to $p$, while $p$ itself is not. Therefore

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

For example,

$$
\varphi(7)=6.
$$

This corresponds to the fact that modulo a prime $p$, every nonzero residue class has a multiplicative inverse.

## Prime Powers

Let $p$ be prime and let $\alpha\ge1$. We compute

$$
\varphi(p^\alpha).
$$

Among the integers

$$
1,2,\ldots,p^\alpha,
$$

the ones not coprime to $p^\alpha$ are exactly the multiples of $p$. There are

$$
p^{\alpha-1}
$$

such multiples:

$$
p,2p,3p,\ldots,p^{\alpha-1}p.
$$

Hence

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

Equivalently,

$$
\varphi(p^\alpha)=p^\alpha\left(1-\frac1p\right).
$$

For example,

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

Indeed, the integers

$$
1,3,5,7
$$

are coprime to $8$.

## Multiplicativity

The totient function is multiplicative. If

$$
\gcd(m,n)=1,
$$

then

$$
\varphi(mn)=\varphi(m)\varphi(n).
$$

This follows from the Chinese remainder theorem. When $m$ and $n$ are coprime,

$$
\mathbb{Z}/mn\mathbb{Z}
\cong
\mathbb{Z}/m\mathbb{Z}
\times
\mathbb{Z}/n\mathbb{Z}.
$$

A residue class modulo $mn$ is invertible exactly when its images modulo $m$ and modulo $n$ are both invertible. Therefore the number of units modulo $mn$ is the product of the number of units modulo $m$ and modulo $n$.

Thus

$$
\varphi(mn)=\varphi(m)\varphi(n).
$$

## Formula from Prime Factorization

Let

$$
n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}
$$

be the canonical prime decomposition of $n$. Since the prime powers are pairwise coprime, multiplicativity gives

$$
\varphi(n) =
\varphi(p_1^{\alpha_1})
\varphi(p_2^{\alpha_2})
\cdots
\varphi(p_r^{\alpha_r}).
$$

Using the prime-power formula,

$$
\varphi(p_i^{\alpha_i}) =
p_i^{\alpha_i}\left(1-\frac1{p_i}\right),
$$

we obtain

$$
\varphi(n) =
n\prod_{p\mid n}\left(1-\frac1p\right).
$$

The product is over the distinct prime divisors of $n$.

For example,

$$
12=2^2\cdot3.
$$

Thus

$$
\varphi(12) =
12\left(1-\frac12\right)\left(1-\frac13\right) =
4.
$$

The coprime integers from $1$ to $12$ are

$$
1,5,7,11.
$$

## Totient and Units

The function $\varphi(n)$ has an algebraic meaning:

$$
\varphi(n)=|(\mathbb{Z}/n\mathbb{Z})^\times|.
$$

That is, $\varphi(n)$ is the number of units modulo $n$.

For example,

$$
(\mathbb{Z}/10\mathbb{Z})^\times =
\{[1],[3],[7],[9]\},
$$

so

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

This interpretation connects elementary counting with finite group theory.

## Euler's Theorem

Euler's theorem states that if

$$
\gcd(a,n)=1,
$$

then

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

This generalizes Fermat's little theorem, which is the special case where $n=p$ is prime:

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

when

$$
p\nmid a.
$$

Euler's theorem follows because the units modulo $n$ form a finite multiplicative group of size $\varphi(n)$. Powers of any unit eventually return to the identity in a structured way.

## Sum over Divisors

The totient function satisfies the important identity

$$
\sum_{d\mid n}\varphi(d)=n.
$$

One way to see this is to classify the integers

$$
1,2,\ldots,n
$$

according to their greatest common divisor with $n$.

For each divisor $d\mid n$, the number of integers $a$ with

$$
1\le a\le n
$$

and

$$
\gcd(a,n)=\frac nd
$$

is

$$
\varphi(d).
$$

Adding over all divisors $d\mid n$ counts each integer from $1$ to $n$ exactly once. Therefore

$$
\sum_{d\mid n}\varphi(d)=n.
$$

For example, if

$$
n=6,
$$

then

$$
\varphi(1)+\varphi(2)+\varphi(3)+\varphi(6) =
1+1+2+2 =
6.
$$

## Role in Number Theory

Euler's totient function measures the invertible part of modular arithmetic. It counts the residue classes that can be divided by, and it controls many exponent laws modulo $n$.

It appears in Euler's theorem, primitive roots, reduced residue systems, RSA cryptography, Dirichlet characters, and multiplicative number theory.

The main idea is that $\varphi(n)$ records how much of arithmetic modulo $n$ remains multiplicatively reversible.