Euler's phi function
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000: Euler's phi (or totient) function of a positive integer n is the number of integers in {1,2,3,...,n} which are relatively prime to n. This is usually denoted phi(x), but for those with non-graphical browsers we often use phi(n) on these pages.

integer n 123456 78 91011121314 1516
phi(n) 112242 64 64104126 88

Clearly for primes p, phi(p)=p-1. Since phi(x) is a multiplicative function, its value can be determined from its value at the prime powers:

Theorem
If p is prime and n is any positive integer, then phi(pn) is pn-1(p-1).

See Also: EulersTheorem

Chris Caldwell © 1999-2009 (all rights reserved)