Euler's Totient function

Content

  • Euler function

Definition

Euler's Totient function $$\phi (n)$$ (sometimes denoted $$\varphi(n)$$ or $${\it phi}(n)$$) is the number of numbers from 1 to $$n$$, coprime with $$n$$. In other words, this is the number of numbers in the interval $$[1; n]$$, the greatest common divisor of which with $$n$$ equals one.

The first few values of the function:

$$\phi(1) = 1$$

$$\phi(2) = 1$$

$$\phi(3) = 2$$

$$\phi(4) = 2$$

$$\phi(5) = 4$$

Properties

The following three simple properties of the Euler function are enought to learn how to calculate it for any number:

  • If $$p$$ is a prime number, then $$\phi(p) = p - 1$$

    (This is obvious, because any number except itself $$p$$, is coprime to it)

  • If $$p$$ is a positive integer, $$a$$ is a natural number, then $$\phi (p^a)=p^a-p^{a-1}$$

    (Since the number of $$p^a$$ are not only relatively prime number of the form $$pk(k \in \mathcal{N})$$ which $$p^a/p = p^{a - 1}$$ numbers)

  • If $$a$$ and $$b$$ are coprime, then $$\phi(ab) = \phi(a)\phi(b)$$ (multiplicativity in Euler's function) (This fact follows from the theorem of China. Consider an arbitrary number $$z \le ab$$. Let $$x$$ and $$y$$ be the remainders of the division $$z$$ into $$a$$ and $$b$$ respectively. Then $$z$$ is coprime to $$ab$$ if and only if $$z$$ coprime to $$a$$ and $$b$$ individually, in other words, $$x$$ coprime to $$a$$ and $$y$$ coprime to $$b$$