Euler's totient function

From Conservapedia

Jump to: navigation, search

The totient function \varphi of a positive integer n is the number of integers k less than n which have no factors in common with n (i.e. such that the greatest common divisor of k and n is 1). For example, the numbers 1, 5, 7, and 11 have no factors in common with 12, so \varphi(12)=4. The totient function can be computer from a prime factorization of n using the formula

\varphi \left( p_1^{k_1} \cdots p_n^{k_n} \right) = (p_1-1)p_1^{k_1-1} \cdot \cdots \cdot (p_n-1)p_n^{k_n-1}.

Some properties of the totient function

  • For a prime number p, all numbers less than p are coprime to it, so \varphi(p) = p -1.
  • For every n, \varphi(n) \leq n-1. This is because there are only n − 1 numbers less than n.
  • The totient may also be bounded below: for n > 6 it satisfies \varphi(n) > \sqrt{n}. \
  • A sharper bound is
\varphi(n) > \frac{n}{e^\gamma \log \log n + \frac{3}{\log \log n}}
  • How fast does the totient function grow? For large n, \phi(n) \approx n "on average". One way to make this precise is by stating  \frac{1}{n^2} \sum_{k=1}^n \varphi(k) = \frac{3}{\pi^2}  + O \left( \frac{\log n}{n} \right), while in contrast  \frac{1}{n^2} \sum_{k=1}^n k = \frac{1}{2} + O \left( \frac{1}{n} \right).
Personal tools