Euler's totient function

The first thousand values of$\phi (n)$

Innumber theory,thetotientof apositiveintegernis the number of positive integers smaller thannwhich arecoprimeton(they share nofactorsexcept 1). It is often written as$\phi (n)$.

For example,$\phi (8)=4$,because there are four numbers (1, 3, 5 and 7) which do not share any factors with 8. Thefunction$\phi$used here is thetotient function,usually called theEuler totientorEuler's totient,after theSwissmathematicianLeonhard Euler,who studied it. The totient function is also calledEuler's phi functionor simply thephi function,since the Greek letterPhi($\phi$) is so commonly used for it. Thecototientofnis defined as$n-\phi (n)$.

The totient function is important mainly because it gives the size of the multiplicativegroupof integersmodulon.More precisely,$\phi (n)$is the order of the group ofunitsof thering$\mathbb {Z} /n\mathbb {Z}$.This fact, together withLagrange's theorem,provides a proof forEuler's theorem.

A common use of the totient function is in theRSA algorithm.The RSA algorithm is a popular method of encryption used worldwide.

For any prime number,p,$\phi (p)=p-1$.

Related pages

• Euler's totient theorem