|
|
The following properties of the Euler 'phi' function are troubling me: I am
using the word phi instead of the standard notation, so forgive me in
advance.
(i) Prove that the Euler phi function is multiplicative:
This isn't too bad, I think it is best done with the principle of inclusion
exclusion. Although someone might have a method I have not considered?
(ii) For any positive integers m and n
prove phi(mn)= phi(m).phi(n).(d/phi(d))
where d is the gcd of m and n.
I think the multiplicative nature makes the m and n parts doable, what
happens with d/phi(d)?
(iii) For any positive integers m and n
prove phi(m).phi(n)= phi(gcd(m,n)).phi(lcm(m,n))
It might be possible to use the fact that gcd(m,n)lcm(m,n) = mn? Or does
that move away from the multiplicativity?
(iv) Take n to be a positive integer greater than 1. Prove that the sum of
the integers m with 1<=m<=n that are coprime with n is (n.phi(n))/2
Not sure where this is going?
|
|