Euler Totient Function

Counting Coprime Residues

Euler’s totient function is an arithmetic function denoted by

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

and

Thus

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

Therefore

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

Prime Moduli

If $p$ is prime, then every integer

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

For example,

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

Among the integers

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

such multiples:

Hence

Equivalently,

For example,

Indeed, the integers

are coprime to $8$.

Multiplicativity

The totient function is multiplicative. If

then

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

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

Formula from Prime Factorization

Let

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

Using the prime-power formula,

we obtain

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

For example,

Thus

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

Totient and Units

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

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

For example,

so

This interpretation connects elementary counting with finite group theory.

Euler’s Theorem

Euler’s theorem states that if

then

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

when

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

One way to see this is to classify the integers

according to their greatest common divisor with $n$.

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

and

is

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

For example, if

then

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.