Let n be a positive integer Euler\'s totient function phi (n) gives the number o
ID: 3123082 • Letter: L
Question
Let n be a positive integer Euler's totient function phi (n) gives the number of positive integers less than or equal to n which are relatively prime to n In this exercise you will prove that phi is given by the formula phi (n) = n*(1 - 1/p_1) (1 - 1/p_2) ellipsis (1 - 1/p_k) where p_1, ellipsis p_k are all the prime divisors of n. The following steps should be useful: If p is a prime number, then phi (p) = p - 1. If p is a prime number and k is a positive integer, then phi (p^k) = p^k - p^k - 1. If m and if n are relatively prime to each other, then phi (mn) = phi (m) phi (n). Use the previous steps to prove the general formula for phi(n).Explanation / Answer
Since p1, p2, p3.....pk are prime factors of n let us write
n = p1a1 * p2a2* p3a3 .... pkak
=> (n) = (p1a1 * p2a2* p3a3 .... pkak)
Since p1, p2, p3.....pk, they are also relatively prime to each other and so are their powers.
So using the identity,
(mn) = (m)*(n)
we have
(n) = (p1a1) * (p2a2) * (p3a3 ).... (pkak)
Further for prime p and integer k we have the identity
(pk) = pk - pk-1 = pk - pk/p = pk (1-1/p)
Using the above identity
(n) = p1a1 (1-1/p1) * p2a2 (1-1/p2) * p3a3 (1-1/p3) ........ pkak (1-1/pk)
=> (n) = (p1a1 p2a2 p3a3 ...... pkak) (1-1/p1) * (1-1/p2) * (1-1/p3) ........ (1-1/pk)
=> (n) = n (1-1/p1) * (1-1/p2) * (1-1/p3) ........ (1-1/pk)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.