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

From ProofWiki
Jump to navigation Jump to search

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 Prime Power:

$\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

From Euler Phi Function is Multiplicative:

\(\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$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Euler_Phi_Function/Examples/1,000,000/Proof_1&oldid=545307"