derivation of Euler phi-function

In this “proof” we will construct the solution for the Euler phi-function, ϕ(n)=np|n(1-1n).

We will do this for the natural numberMathworldPlanetmath n>0. Keep in mind that gcd(a,n)=1 a is not divisible by p for all primes p dividing n.

Let n2 and p1,p2,,pr be all prime divisorsPlanetmathPlanetmath of n. Let N={a0a<n,gcd(a,n)=1} and Ai:={a0a<n,pi|a}. If J{1,2,,r} than pJ:=jJpi.

Thus, #(AJ)=#(jJAj)=#({aA:pJ|a})=npJ

Using inclusion-exclusion,


Title derivation of Euler phi-function
Canonical name DerivationOfEulerPhifunction
Date of creation 2013-03-22 17:42:52
Last modified on 2013-03-22 17:42:52
Owner jwaixs (18148)
Last modified by jwaixs (18148)
Numerical id 22
Author jwaixs (18148)
Entry type DerivationPlanetmathPlanetmath
Classification msc 11-00