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.

Title	Euler phi function
Canonical name	EulerPhiFunction
Date of creation	2013-03-22 11:45:11
Last modified on	2013-03-22 11:45:11
Owner	Wkbj79 (1863)
Last modified by	Wkbj79 (1863)
Numerical id	19
Author	Wkbj79 (1863)
Entry type	Definition
Classification	msc 11A25
Classification	msc 11-00
Classification	msc 14F35
Classification	msc 14H30
Classification	msc 20F34
Synonym	Euler totient function
Synonym	Euler $\phi$ function
Synonym	Euler $\varphi$ function
Related topic	ProofThatEulerPhiIsAMultiplicativeFunction
Related topic	ValuesOfNForWhichVarphintaun
Related topic	PrimeResidueClass
Related topic	EulerPhiAtAProduct
Related topic	SummatoryFunctionOfArithmeticFunction