Euler phi function

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

Among the most useful properties of $\varphi$ are the facts that it is multiplicative (meaning if $\gcd(a,b)=1$ , then $\varphi(ab)=\varphi(a)\varphi(b)$ ) and that $\varphi(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 $\varphi$ for all positive integers:

For example,
From equation (), it is clear that $\varphi(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 Euler $\varphi$ function is that$$ \sum_{d|n} \varphi(d)=n,$$ where the sum extends over all positive divisors of $n$ . Also, by definition, $\varphi(n)$ is the number of units in the ring $\mathbb{Z}/n\mathbb{Z}$ of integers modulo $n$ .

The sequence $\{\varphi(n)\}$ appears in the OEIS as sequence A000010.