## You are here

HomeEuler phi function

## Error message

*Notice*: Trying to get property of non-object in*question_unanswered_block()*(line*404*of*/home/jcorneli/beta/sites/all/modules/question/question.module*).*Notice*: Trying to get property of non-object in*question_unanswered_block()*(line*404*of*/home/jcorneli/beta/sites/all/modules/question/question.module*).*Notice*: Trying to get property of non-object in*question_unanswered_block()*(line*404*of*/home/jcorneli/beta/sites/all/modules/question/question.module*).*Notice*: Trying to get property of non-object in*collection_incollection_block()*(line*709*of*/home/jcorneli/beta/sites/all/modules/collection/collection.module*).*Notice*: Trying to get property of non-object in*collection_incollection_block()*(line*709*of*/home/jcorneli/beta/sites/all/modules/collection/collection.module*).*Notice*: Trying to get property of non-object in*collection_incollection_block()*(line*709*of*/home/jcorneli/beta/sites/all/modules/collection/collection.module*).

## Primary tabs

# 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:

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

## Mathematics Subject Classification

11A25*no label found*11-00

*no label found*14F35

*no label found*14H30

*no label found*20F34

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## \phi(x) = 1000

Hi everybody, we can now introduce an interesting year x satisfying the above equation. Good new year!

Jussi