Euler phi function

For any positive integer $n$, $\phi (n)$ is the number of positive integers less than or equal to $n$ which are coprime to $n$. The function $\phi$ is known as the $\phi$ function. This function may also be denoted by $\varphi$.

Among the most useful of $\phi$ are the facts that it is multiplicative (meaning if $\gcd (a,b)=1$, then $\phi (ab)=\phi (a)\phi (b)$) and that $\phi (p^k)=p^{k-1}(p-1)$ for any prime $p$ and any positive integer $k$. These two facts combined give a numeric computation of $\phi$ for all positive integers:

$\phi (n)$$=n{\displaystyle \prod _{p|n}}\left(1-{\displaystyle \frac{1}{p}}\right).$(1)

For example,

$\phi (2000)$$=2000{\displaystyle \prod _{p|2000}}\left(1-{\displaystyle \frac{1}{p}}\right)$

$=2000\left(1-{\displaystyle \frac{1}{2}}\right)\left(1-{\displaystyle \frac{1}{5}}\right)$

$=2000\left({\displaystyle \frac{1}{2}}\right)\left({\displaystyle \frac{4}{5}}\right)$

$={\displaystyle \frac{8000}{10}}$

$=800.$

From equation (1), it is clear that $\phi (n)\le n$ for any positive integer $n$ with equality holding exactly when $n=1$. This is because

$$\prod _{p|n}\left(1-\frac{1}{p}\right)\le 1,$$

with equality holding exactly when $n=1$.

Another important fact about the $\phi$ function is that

$$\sum _{d|n}\phi (d)=n,$$

where the sum extends over all positive divisors of $n$. Also, by definition, $\phi (n)$ is the number of units in the ring $\mathbb{Z}/n\mathbb{Z}$ of integers modulo $n$.

The sequence $\{\phi (n)\}$ appears in the OEIS as sequence http://www.research.att.com/ njas/sequences/A000010A000010.