# 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 $\varphi$ function. This function may also be denoted by $\phi$.

Among the most useful 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:

 $\displaystyle\varphi(n)$ $\displaystyle=n\prod_{p|n}\left(1-\frac{1}{p}\right).$ (1)

For example,

 $\displaystyle\varphi(2000)$ $\displaystyle=2000\prod_{p|2000}\left(1-\frac{1}{p}\right)$ $\displaystyle=2000\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)$ $\displaystyle=2000\left(\frac{1}{2}\right)\left(\frac{4}{5}\right)$ $\displaystyle=\frac{8000}{10}$ $\displaystyle=800.$

From equation (1), it is clear that $\varphi(n)\leq 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)\leq 1,$

with equality holding exactly when $n=1$.

Another important fact about the $\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 http://www.research.att.com/ njas/sequences/A000010A000010.

Title Euler phi function EulerPhiFunction 2013-03-22 11:45:11 2013-03-22 11:45:11 Wkbj79 (1863) Wkbj79 (1863) 19 Wkbj79 (1863) Definition msc 11A25 msc 11-00 msc 14F35 msc 14H30 msc 20F34 Euler totient function Euler $\varphi$ function Euler $\phi$ function ProofThatEulerPhiIsAMultiplicativeFunction ValuesOfNForWhichVarphintaun PrimeResidueClass EulerPhiAtAProduct SummatoryFunctionOfArithmeticFunction