Euler's phi function

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 φ(n).

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

Clearly for primes p, φ(p)=p-1. Since φ(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 φ(pn) is pn-1(p-1).

See Also: EulersTheorem

Printed from the PrimePages <t5k.org> © Reginald McLean.