Euler’s Totient Function

Euler’s totient function counts the number of positive integers up to $n$ that are relatively prime to $n$, where $1$ is considered to be relatively prime to all $n$.  These numbers are called the totatives of $n$.

The totient function is denoted by $\varphi(n)$.

$\varphi(p) = p-1$, for a prime $p$.

Euler’s product formula for the function is :

$\displaystyle \varphi(n) = n\prod_{p|n}\Bigl(1-\frac 1p \Bigr)$,

where $p|n$ are the distinct primes that divide the given number and $\prod$ is the product over them.

For example, $12 = 2^2 \cdot3$

$\displaystyle \varphi(12) = 12\Bigl(1-\frac12 \Bigr)\Bigl(1-\frac 13 \Bigr)$

$\displaystyle = 12 \cdot \frac12 \cdot \frac23 = 4$

The totatives of $12$  are $1, 5, 7$ and $11$.

$\displaystyle \varphi(13) = 13\Bigl(1-\frac{1}{13}\Bigr)$

$\displaystyle = 13 \cdot  \frac{12}{13}  = 12$

The totatives of $13$ are all the numbers less than $13$.

$\displaystyle \varphi(30) = 30\Bigl(1-\frac12\Bigr)\Bigl(1-\frac13\Bigr)\Bigl(1-\frac15\Bigr)$

$\displaystyle = 30 \cdot \frac12 \cdot \frac23 \cdot \frac45 = 8$

The totatives of $30$ are $1, 7, 11, 13, 17, 19, 23$ and $29$.

The first few values for $\varphi(n)$ :

$\begin{array}{c|cccccccccccc} n&1&2&3&4&5&6&7&8&9&10&11&12 \\ \varphi(n)&1&1&2&2&4&2&6&4&6&4&10&4 \end{array}$

A graph of the first thousand values :

Euler’s phi function has the important property of being a multiplicative function.  That is, whenever $m$ and $n$ are two relatively prime integers (gcd$(m, n) = 1$) , then

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

This aids speed of computation, for example,

$\varphi(35) = \varphi(5)\varphi(7) = 4\cdot6 = 24$

Another property of the function is the prime power argument :

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

for prime $p$ and $\alpha \geq 1$.

For example,

$\varphi(2^6) = 2^6-2^5 = 64-32 = 32$

and

$\varphi(5^3) = 5^3-5^2 = 125-25 = 100$.

Gauss established another identity that relates the divisors of $n$ to $n$ via the formula

$\displaystyle \sum_{d|n} \varphi(d) = n$

where $d|n$ are the divisors of n and $\sum \varphi(d)$ is the sum of the totients of the divisors.

For example, the divisors of $12$ are $1, 2, 3, 4, 6$ and $12$ which have totients $1, 1, 2, 2, 2, 4$.

Now, $1 + 1 + 2 + 2 + 2 + 4 = 12$ so

$\displaystyle \sum_{d|12} \varphi(d) = 12$

For a prime number the sum is very simple.  For example, the divisors of $13$ are $1$ and $13$ which have totients $1$ and $12$ and $1 + 12 = 13$.

Euler generalised Fermat’s Little Theorem.

Euler’s Theorem states :

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

where $a$ and $n$ are relatively prime $(gcd(a, n) = 1)$.

The special case where $n$ is prime is Fermat’s Little Theorem :

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

Fermat’s Little Theorem

 

© OldTrout $2018$