Euler's totient function

From Conservapedia

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).$

Euler's totient function

From Conservapedia

Some properties of the totient function

Views

Personal tools

Search

Popular Links

Help

World History

Edit Console