The definition and key theorems involving Euler's Totient function. For more info, see the "related pages" listed below.
φ(n) is the number of positive integers not larger than n that are coprime to n. (Coprime is defined this way: two numbers are coprime when they share no factor other than 1.) Note that φ(1)=1, because 1 is coprime to itself.
Let x = p1e1 p2e2 ... pnen
φ(x) = x (1-1/p1) ( 1-1/p2)...( 1-1/pn)
(1) Totient is a multiplicative function -- that means when a and b are coprime (i.e. GCD(a,b)=1), then φ(ab) = φ(a) φ(b).
(2) If p is prime then φ(pn) = pn-1(p-1), so
(3) φ(x) = p1e1-1 (p1-1) p2e2-1 ( p2-1)...pnen-1 ( pn-1), which simplifies to the expression given here, as explained by the Totient Function page.
Consider the sum,
Σ φ(d) = n
Proof: I will show that this sum counts all the cases, as k ranges from 1 to n, in which GCD(k,n)=d, where d is a divisor of n. There are n such cases, because GCD(k,n) is always some divisor of n.
As k ranges from 1 to n, GCD(k,n)=d exactly when k/d and n/d are coprime integers. Therefore, the sum
Σ φ(n/d) = n
And, since n/d ranges over all the factors of n, this sums the totients of all the factors of n, proving the result.
A more elaborate proof with examples: Totient Function
Proof: Euler's Totient Theorem
Proof that the sum of totients of divisors of n is n: Totient Function, and some other interesting things about totients.
Proof that any number coprime to n raised to the power φ(n) is 1 (mod n): Euler's Totient Theorem, and some other interesting things about totients.
Method of proof: multiplicative induction
μ(n), the M�bius function
τ(n), the number of divisors of n: Divisors, Tau function
The webmaster and author of this Math Help site is Graeme McRae.