Euler's totient function, first found by Leonhard Euler, is a function that yields the number of totatives of an integer greater than 1. It is related to number theory. Note that a totative is a relative prime less than or equal to a number. For instance, 15 is a totative of 16.
Notation[]
The function is usually denoted as φ(n), a notation Gauss found after Euler formulated the function. It was first introduced as Euler's phi function or simply the phi function before Sylvester came up with the term "totient" for the function.
Obtaining a formula[]
Euler came up with a product formula for the totient function. It can be stated as
Obtaining this formula has several methods. The most simple is by mathematical induction. Let's assume p is a prime factor of x. Obviously, there are x/p integers that are divisable by p and smaller than or equal to x. So the number of the integers not satisfying this must be .
Now let's assume that q is also a prime that divides x. Obviously, there are x/q integers that are divisable by q and smaller than or equal to x, as the previous case. However, these duplicate x/pq integers, because we counted some integers both in the prime p and prime q. Hence, the true number we need to take out becomes x(1/q - 1/pq). Subtracting, we get
.
Induction then yields the formula we have given easily.
Multiplicativity of φ(x)[]
The following is true for all integers with gcd(a,b) = 1, or in words, for all integers that are relatively prime: φ(ab)=φ(a)φ(b).
To verify this, it is enough to observe that if a and b are relatively prime, their divisor sets are separate, hence the primes that are dividing them must be different. This simple observation then yields the following equalities:
The first equality follows from Euler's formula for the totient, the second equality follows from the fact that the primes dividing a and b are different and the third equality, again, follows from Euler's formula for the totient.
Finding a statement equivalent to being a prime[]
As easily shown, if φ(x) = x-1, then x is prime. This follows from the fact that every number smaller than the prime is a totative of the prime, but the prime itself. So we obtain p-1 totatives, -1 being present for the prime is not a totative of itself.
Proving a weaker version of the PNT[]
We will prove that the density of the primes in natural numbers is zero. For this, we will use the statement we found in the above section. Proving this equality is enough:
Let's prove this:
The fourth equality follows from Euler's product formula, where ζ(x) denotes the Riemann zeta function. Since ζ(1) = ∞, or in asymptotic terms, ζ(x) has a simple pole at x=1, the last equality holds.