Euler phi function (original) (raw)

For any positive integer n, φ⁢(n) is the number of positive integers less than or equal to n which are coprime to n. The function φ is known as the φ function. This function may also be denoted by ϕ.

Among the most useful of φ are the facts that it is multiplicative (meaning if gcd⁡(a,b)=1, then φ⁢(a⁢b)=φ⁢(a)⁢φ⁢(b)) and that φ⁢(pk)=pk-1⁢(p-1) for any prime p and any positive integer k. These two facts combined give a numeric computation of φ for all positive integers:

For example,

From equation (1), it is clear that φ⁢(n)≤n for any positive integer n with equality holding exactly when n=1. This is because

with equality holding exactly when n=1.

Another important fact about the φ function is that

where the sum extends over all positive divisors of n. Also, by definition, φ⁢(n) is the number of units in the ring ℤ/n⁢ℤ of integers modulo n.

The sequence {φ⁢(n)} appears in the OEIS as sequence http://www.research.att.com/ njas/sequences/A000010A000010.