PlanetMath: Euler phi function

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Euler phi function

(Definition)

For any positive integer , $\varphi(n)$ is the number of positive integers less than or equal to which are coprime to . 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 and any positive integer . These two facts combined give a numeric computation of $\varphi$ for all positive integers:

$\displaystyle \varphi(n)$

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

(1)

For example,

$\displaystyle \varphi (2000)$	$\displaystyle = 2000 \prod_{p\vert 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)\le n$ for any positive integer with equality holding exactly when . This is because

$\displaystyle \prod_{p\vert n} \left( 1-\frac{1}{p} \right) \le 1,$

with equality holding exactly when

Another important fact about the Euler $\varphi$ function is that

$\displaystyle \sum_{d\vert n} \varphi(d)=n,$

where the sum extends over all positive divisors of

. Also, by definition, $\varphi(n)$ is the number of units in the ring $\mathbb{Z}/n\mathbb{Z}$ of integers modulo

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

"Euler phi function" is owned by Wkbj79. [ full author list (2) | owner history (1) ]

(view preamble)

See Also: proof that Euler $\varphi$ function is multiplicative, values of $n$

for which $\varphi(n)=\tau(n)$ , prime residue class

Other names:

Euler totient function, Euler $\varphi$ function, Euler $\phi$ function

Keywords:

number theory

Attachments:: derivation of Euler phi-function (Derivation) by jwaixs

Log in to rate this entry.
(view current ratings)

Cross-references: OEIS, sequence, ring, units, divisors, sum, equality, clear, equation, prime, multiplicative, function, coprime, number, integer, positive
There are 39 references to this entry.

This is version 14 of Euler phi function, born on 2001-10-15, modified 2008-05-28.
Object id is 196, canonical name is EulerPhifunction.
Accessed 31970 times total.

Classification:

AMS MSC:	11-00 (Number theory :: General reference works )
	11A25 (Number theory :: Elementary number theory :: Arithmetic functions; related numbers; inversion formulas)

Pending Errata and Addenda

None.[ View all 7 ]

Discussion

forum policy

Interact