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	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
φ(n)	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8

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 φ(pⁿ) is p^n-1(p-1).

See Also: EulersTheorem