|
|
Brendan O'Sullivan <bos4@xxxxxxxxxxxx> wrote:
> 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?
I would use the Chinese remainder theorem.
> (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.
> (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?
--
Daniel W. Johnson
panoptes@xxxxxxxxxx
http://members.iquest.net/~panoptes/
039 53 36 N / 086 11 55 W
|
|