"The poet only asks to get his head into the heavens. It is the logician who seeks to get the heavens into his head. And it is his head that splits." G.K. Chesterton

Monday, May 23, 2011

Number Theory 3: A formula for calculating Euler's phi function

Below is a proof for calculating phi (Euler’s function) for any natural number. Phi(m) is defined to be the number of all natural numbers n less than m that are relatively prime to it i.e. each such n<m satisfies gcd(n,m)=1.
The p’s in the above formula denote primes. The proof will be relatively simple, as it will use the following fundamental results, where p denotes a prime and m and n are relatively prime.:
 By the Fundamental Theorem of Arithmetic we express m in terms of its unique prime factorization,

 Re writing the expression and, by associative law, multiplying the first two terms we have the following,

and substituting m’s prime factorization yields,

Further algebraic manipulation gives,

Now, by repeated use of associative law, factoring out each consecutive prime in m’s factorization and multiplying it by the term from the original formula where that prime appears,

leaves us with the product rearranged to the following form,

Finally we resort to (*), and (**) to get

No comments: