In number theory, Euler’s totient function, also be called Euler’s phi function \( \varphi(n) \) counts the positive integers up to a given integer n that are relatively prime to n.
\( \varphi(1)=1 \)
\( \varphi(mn)=\varphi(m)\varphi(n) \hspace{16 pt} whenever \hspace {8pt} m \bot n \hspace {8pt} i.e. \hspace {8pt} gcd(m, n)=1 \)
Si sint A et B numeri inter se primi et numerus partium ad A primarum sit = a, numerus vero partium ad B primarum sit = b, tum numerus partium ad productum AB primarum erit = ab. - L. Euler
Outline of proof: let A, B, C be the sets of nonnegative integers, which are, respectively, coprime to and less than m, n, and mn; then there is a bijection between A × B and C, by the Chinese remainder theorem.
Concrete Mathematics p144
NUMBER THEORY - Exercises - Warmups - 10 Compute \( \phi(999) \).
\( \phi(p)=p-1 \)
\( \phi(p^k)=p^k-p^{k-1} \)
\( \phi(999)=\phi(3^3 \times 37) \)
\( =\phi(3^3) \times \phi(37) = (3^3-3^2) \times 36 = 648 \)
\( \phi(666) = 216 = 6 \times 6 \times 6 \)
- Euler’s Phi Function and the Chinese Remainder Theorem
- Computing the Euler totient function, part 1
- Computing the Euler totient function, part 2: seeing phi is multiplicative
- Computing the Euler totient function, part 3: proving phi is multiplicative
- Computing the Euler totient function, part 4: totient of prime powers
- Euler’s totient function