The Euler totient function
φ |

The * Euler function*, or

The Euler function *φ*: **N** → **N** is a mapping associating to each
positive integer *n* the number *φ*(*n*) of integers *m* *n*
relatively prime to *n*.
(In other words: *φ*(*n*) is the number of positive integers
*m* *n* with gcd(*m*, *n*) = 1.)
E.g., *φ*(6) = 2 (since only 1 und 5 are relatively prime to 6), or
*φ*(15) = 8 (for 1, 2, 4, 7, 8, 11, 13, and 14 are relatively prime to 15).
The following table shows the function values for the first natural numbers.

n |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

φ(n) |
1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 | 12 | 6 | 8 |

Do you discover some formation rule? If so, you should go on researching, because
you could solve number theoretic problems being open so far...
If not, you might be interested in some of the most important properties of the
Euler function. The first one is that there exists a formula to compute
*φ*(*n*): If the prime factorization of *n* is given by
*n* = *p*_{1}^{a1} ...
*p _{k}^{ak}*, we have

φ(n) =
n (1 - 1/p_{1})
... (1 - 1/p).
_{k} |

Example:
12 = 2^{2} · 3, i.e.
*φ*(12) = 12 · (1 - 1/2) · (1 - 1/3) = 12 · 2 / (2 · 3) = 4.
A further property of the totient function is the
* sum formula*: The sum over
the Euler function values

*φ*(1) + *φ*(2) + *φ*(3) + *φ*(4) +
*φ*(6) + *φ*(12)
= 1 + 1 + 2 + 2 + 2 + 4 = 12.

Moreover, the
order ord_{n}(*m*)
of an integer *m* modulo *n* always divides *φ*(*n*).
Closely related to the Euler function is the
Carmichael function *λ*.

- Friedhelm Padberg:
*Elementare Zahlentheorie*. Spektrum Akademischer Verlag, Heidelberg Berlin 1996 - Hans Riesel:
*Prime Numbers and Computer Methods for Factorization*. Birkhäuser Boston Basel Berlin 1994

© de Vries 2002 |