Results 1 to 6 of 6

Math Help - Euler's phi-function.

  1. #1
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    Euler's phi-function.

    Challange Problem.
    Prove that \displaystyle\frac{\phi(m)}{m}=\frac{\phi(n)}{n} if and only if m and n share exactly the same prime divisors.

    Moderator approved CB
    Last edited by CaptainBlack; September 30th 2010 at 11:35 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Let  m = \prod_i p_i^{a_i} and  n = \prod_i q_i^{b_i} ( prime factorization of  m and  n respectively . )

    We know  \frac{\phi(m)}{m}  = \prod_i \left( 1 - \frac{1}{p_i} \right) , it is obvious that if  m and  n share the same prime divisors , the product   \prod_i \left( 1 - \frac{1}{p_i} \right)  should equal  \prod_i \left( 1 - \frac{1}{q_i} \right) as we can find a bijection linking  \{\ p_1 , p_2 ,... \}\ and  \{\ q_1 , q_2 ,... \}\ .

    Suppose for  \frac{ \phi(m) }{m} = \frac{ \phi(n) }{n} , they don't share all the same prime divisors , let  m = m' d ~,~ n=n' d , where d is the greatest common divisor of them . Now  m' and  n' are relatively prime and not equal to 1 ( if so , the other must also be  1 , then m=n=d , a contradiction . )

    Let  \prod_i \left( 1 - \frac{1}{p_i} \right)  and  \prod_i \left( 1 - \frac{1}{q_i} \right) be the prime factorization of  m' and  n' respectively .

    Consider  q_1 q_2 ... (p_1 - 1 )(p_2 - 1 ) ... = p_1 p_2 ... (q_1 -1 )(q_2 - 1 ) ...     ,

    since  p_1 , p_2 ,... , q_1 ,q_2 ,... are distinct , we must have  p_1 p_2 ... | (p_1 - 1 )(p_2 - 1 ) ... and  q_1 q_2 ... | (q_1 - 1 )(q_2 - 1 ) ... .  \prod_i \left( 1 - \frac{1}{p_i} \right) and   \prod_i \left( 1 - \frac{1}{q_i} \right)  are less than  1 but in this case they are positive integers , this leads to a contradiction .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by simplependulum View Post
    Let  \prod_i \left( 1 - \frac{1}{p_i} \right)  and  \prod_i \left( 1 - \frac{1}{q_i} \right) be the prime factorization of  m' and  n' respectively .

    Consider  q_1 q_2 ... (p_1 - 1 )(p_2 - 1 ) ... = p_1 p_2 ... (q_1 -1 )(q_2 - 1 ) ...     ,
    I understand that you set \frac{\phi(m')}{m'}=\frac{\phi(n')}{n'} and then arrived at q_1q_2...(p_1-1)(p_2-1)...= p_1p_2...(q_1-1)(q_2-1).
    If I understood correctly, then I don't see why it's true that \frac{\phi(m')}{m'}=\frac{\phi(n')}{n'}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by melese View Post
    I understand that you set \frac{\phi(m')}{m'}=\frac{\phi(n')}{n'} and then arrived at q_1q_2...(p_1-1)(p_2-1)...= p_1p_2...(q_1-1)(q_2-1).
    If I understood correctly, then I don't see why it's true that \frac{\phi(m')}{m'}=\frac{\phi(n')}{n'}.
    Well, he arrives at p_1p_2\dots | (p_1-1)(p_2-1)\dots, which implies p_1p_2\dots \leq  (p_1-1)(p_2-1)\dots, which is absurd, right?

    Edit : as melese remarked in a P.M to me, this is not the issue with S.P. 's proof. I'll let him explain!
    Last edited by Bruno J.; October 5th 2010 at 08:31 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Alright. Let m,n be such that \frac{\varphi(m)}{m}=\frac{\varphi(n)}{m}. As simplependulum remarked, we can write this equation as

    \displaystyle \prod_{p\in P}p \prod_{q\in Q}(q-1) = \prod_{q\in Q}q \prod_{p\in P}(p-1),

    where P,Q denote, respectively, the sets of prime divisors of m,n. Now we can divide both members by

    \displaystyle\prod_{u \in P\cap Q}u(u-1),

    after which we are left with

    \displaystyle \prod_{p\in P'}p \prod_{q\in Q'}(q-1) = \prod_{q\in Q'}q \prod_{p\in P'}(p-1),

    where P'=P\backslash Q and Q' = Q\backslash P (so that P' \cap Q' = \emptyset). Now suppose P' \neq \emptyset and take any p \in P'. Since p \notin Q', we must have p | \displaystyle \prod_{p\in P'}(p-1), i.e. p | p'-1 for some p' \in P'. But if you take the greatest p \in P', this is clearly impossible. Hence P' = \emptyset, and similarily Q' = \emptyset, hence P=Q.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    What I wrote is perhaps what S.P. had in mind.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler Phi function II
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 27th 2009, 04:33 AM
  2. Euler Phi-Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 12th 2009, 03:44 AM
  3. euler phi-function
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 29th 2009, 07:42 PM
  4. Euler phi-Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 11th 2009, 06:11 PM
  5. Again, phi euler function
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: January 22nd 2009, 11:35 AM

Search Tags


/mathhelpforum @mathhelpforum