# Euler Phi Function/Examples/1,000,000

## Example of Use of Euler $\phi$ Function

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

where $\phi$ denotes the Euler $\phi$ function.

## Proof 1

We have that:

 $\ds 1\,000\,000$ $=$ $\ds 10^6$ $\ds$ $=$ $\ds 5^6 \times 2^6$
$\map \phi {p^n} = p^n \paren {1 - \dfrac 1 p}$

Thus:

 $\ds \map \phi {5^6}$ $=$ $\ds 5^6 \paren {1 - \dfrac 1 5}$ $\ds$ $=$ $\ds \dfrac 4 5 5^6$ $\ds$ $=$ $\ds 4 \times 5^5$

and:

 $\ds \map \phi {2^6}$ $=$ $\ds 2^5$ Euler Phi Function of Prime Power: Corollary
 $\ds \map \phi {1 \, 000 \, 000}$ $=$ $\ds \map \phi {10^6}$ $\ds$ $=$ $\ds \map \phi {5^6 \times 2^6}$ $\ds$ $=$ $\ds \map \phi {5^6} \map \phi {2^6}$ Euler Phi Function is Multiplicative $\ds$ $=$ $\ds 4 \times 5^5 \times 2^5$ $\ds$ $=$ $\ds 4 \times 10^5$ $\ds$ $=$ $\ds 400 \, 000$

Thus:

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

## Proof 2

We have that:

 $\ds 1\,000\,000$ $=$ $\ds 10^6$ $\ds$ $=$ $\ds 5^6 \times 2^6$
$\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$