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 :
Pietro Battiston (it:User:Toobaz) [CC BY-SA]
\(\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\)
© OldTrout \(2018\)
