|
|
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:
Suppose t = mn where m,n are coprime. Then the chinese remainder theorem
states that (a,t) = 1 if and only if (a,m)=1 and (a,n)=1.
Now the number of positive integers not greater than t and coprime with t
is
precisely phi(t), but it is also the number of pairs (u,v) where u is not
greater than m and coprime with m and v not greater than n and coprime
with
n, thus
phi(mn)=phi(m)phi(n)
(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)?
Note that the case d=1 is equivalent to the first property.
If m and n are not coprime? How does the proof develop?
(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?
As a last resort, you could use the prime factorizations of m and n.
(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?
If m is coprime with n, what can you say about n-m and n? They are also
coprime?
|
|