Wikia

Math Wiki

Euler's totient function

Talk2
667pages on
this wiki
420px-EulerPhi100.svg
The totient function graphed. The blue dots demonstrate the totient function, ignore the blue lines.
Starfall.VAdded by Starfall.V

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.

NotationEdit

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 formulaEdit

Euler came up with a product formula for the totient function. It can be stated as

\varphi (x)=x\prod_{p|x}1-\frac{1}{p}

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 \textstyle x(1-\frac{1}{p}).

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

x\left (\left (1-\frac{1}{p}  \right )-\frac{1}{q}+\frac{1}{pq}\right)

= x\left (\left (1-\frac{1}{p}  \right )-\frac{1}{q}\left(1-\frac{1}{p} \right )\right)

= x\left (1-\frac{1}{p}  \right )\left(1-\frac{1}{q} \right ).

Induction then yields the formula we have given easily.

Multiplicativity of φ(x)Edit

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:

\varphi (a)\varphi (b)=\left (\prod_{p|a}1-\frac{1}{p}  \right )\left ( \prod_{p|b}1-\frac{1}{p} \right )=\prod_{p|ab}1-\frac{1}{p}=\varphi (ab)

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 primeEdit

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 PNTEdit

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: \textstyle \lim_{x \to\infty }\varphi (x)/x=0

Let's prove this:

\lim_{x \to\infty }\varphi (x)/x=\lim_{x \to\infty }\prod_{p|x}1-\frac{1}{p}=\prod_{p-prime}1-\frac{1}{p}=\left ( \prod_{p-prime}\frac{p}{p-1} \right )^{-1}=\zeta ^{-1}(1)=0

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.

Around Wikia's network

Random Wiki