Euler Phi Function/Examples/1,000,000/Proof 2

Example of Use of Euler $\phi$ Function

$\map \phi {1 \, 000 \, 000} = 400 \, 000$

Proof

We have that:

\(\ds 1\,000\,000\)

\(=\)

\(\ds 10^6\)

\(\ds \)

\(=\)

\(\ds 5^6 \times 2^6\)

From Euler Phi Function of Integer:

$\ds \map \phi n = n \prod_{p \mathop \divides n} \paren {1 - \frac 1 p}$

where $p$ denotes a prime number.

So:

\(\ds \map \phi {1\,000\,000}\)

\(=\)

\(\ds 1\,000\,000 \paren {1 - \frac 1 2} \paren {1 - \frac 1 5}\)

\(\ds \)

\(=\)

\(\ds 1\,000\,000 \times \frac 1 2 \times \frac 4 5\)

\(\ds \)

\(=\)

\(\ds 400\,000\)

Thus:

$\map \phi {1\,000\,000} = 400\,000$