Re: Four Properties of the Euler Phi Function

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?


.

Relevant Pages

  • Re: Four Properties of the Euler Phi Function
    ... >> The following properties of the Euler 'phi' function are troubling me: ... Now the number of positive integers not greater than and coprime with is ...
    (sci.math)
  • Re: Four Properties of the Euler Phi Function
    ... >> Prove that the Euler phi function is multiplicative: ... > It's multiplicative only for coprime integers. ... > restricted to the multiplicative groups is an isomorphism. ... >> For any positive integers m and n ...
    (sci.math)
  • Re: Four Properties of the Euler Phi Function
    ... > The following properties of the Euler 'phi' function are troubling me: ... > For any positive integers m and n ... > that move away from the multiplicativity? ...
    (sci.math)
  • Four Properties of the Euler Phi Function
    ... The following properties of the Euler 'phi' function are troubling me: ... For any positive integers m and n ... that move away from the multiplicativity? ...
    (sci.math)
  • Re: eulers phi-function and divisibility by primes
    ... from Euler it is known, that, with a prime p, and a ... Is a case knwon (or is it known that it is ... where, are coprime positive integers, and is odd positive integer greater than one ...
    (sci.math)
Quantcast