Euler's Phi Function

Definition (Euler’s Phi Function)

For a positive integer $n$, let $\varphi (n)$ denote the number of integers $r$ with $0\le r<n$ and $\gcd (r,n)=1$.

Equivalently, $\varphi (n)$ counts the invertible residue classes modulo $n$.

Basic Facts

If $p$ is prime, then

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

since every nonzero residue modulo $p$ is relatively prime to $p$.

More generally,

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

for every prime $p$ and integer $e\ge 1$.

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

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

so $\varphi$ is multiplicative on relatively prime inputs.

Combining this with the prime factorization of $n$, we get

$$\varphi (n)=n\prod _{p\mid n}\left(1-\frac{1}{p}\right)$$

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

Theorem (Euler’s Theorem)

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

$$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$$

This generalizes Fermat’s little theorem when $n$ is prime.

Example

Since $\varphi (15)=15(1-1/3)(1-1/5)=8$, any integer $a$ relatively prime to $15$ satisfies

$$a^8\equiv 1(\mathrm{mod}15)$$