# Euler's totient

• June 30th 2010, 04:54 PM
teramaries
Euler's totient
Suppose p and q are unequal primes. Prove the following:

a. pi(p)=p-1
b. pi(p^2)=p^2-p
c. pi(p^n)=p^n-p^n-1 where n is a positive integer
d. pi(pq)=pq-q-p+1 = (p-1)(q-1)
• June 30th 2010, 06:21 PM
chiph588@
Quote:

Originally Posted by teramaries
Suppose p and q are unequal primes. Prove the following:

a. pi(p)=p-1
b. pi(p^2)=p^2-p
c. pi(p^n)=p^n-p^n-1 where n is a positive integer
d. pi(pq)=pq-q-p+1 = (p-1)(q-1)

Just list all the numbers less than or equal to the input of $\varphi$ and count how many are divisible by the input.