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:
Post a Comment