Results 1 to 13 of 13

Math Help - Euler Totient Function Question

  1. #1
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Euler Totient Function Question

    Hello,
    I just need to know if this holds :

     <br />
a^b \equiv a^{b \mod \varphi{(n)}} \pmod{n}<br />
For any a coprime with n.

    I know this is true but what about this :

     <br />
a^{\left ( b^c \right )} \equiv a^{\left ( b^{c \mod \varphi{(\varphi{(n)})}} \right )} \pmod{n}<br />
For any a coprime with n.

    This would seem to work intuitively but I'm having trouble proving or disproving it (all my tests seem to fail for some reason but not because of the math).

    Thank you all
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Bacterius View Post
    Hello,
    I just need to know if this holds :

     <br />
a^b \equiv a^{b \mod \varphi{(n)}} \pmod{n}<br />
For any a coprime with n.

    I know this is true but what about this :

     <br />
a^{\left ( b^c \right )} \equiv a^{\left ( b^{c \mod \varphi{(\varphi{(n)})}} \right )} \pmod{n}<br />
For any a coprime with n.

    This would seem to work intuitively but I'm having trouble proving or disproving it (all my tests seem to fail for some reason but not because of the math).

    Thank you all
    Did you check whether \text{gcd}(b, \varphi(n))=1?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bacterius View Post
    Hello,
    I just need to know if this holds :

     <br />
a^b \equiv a^{b \mod \varphi{(n)}} \pmod{n}<br />
For any a coprime with n.

    I know this is true but what about this :

     <br />
a^{\left ( b^c \right )} \equiv a^{\left ( b^{c \mod \varphi{(\varphi{(n)})}} \right )} \pmod{n}<br />
For any a coprime with n.

    This would seem to work intuitively but I'm having trouble proving or disproving it (all my tests seem to fail for some reason but not because of the math).

    Thank you all
     b^c \bmod{\varphi(\varphi(n))} = b^c+d\varphi(\varphi(n)) for some  d

     a^{b^c+d\varphi(\varphi(n))}=a^{b^c}a^{d\varphi(\v  arphi(n))}\equiv a^{b^c} \bmod{n}

    Since  (a,n)=1\implies (a^{b^c},n)=1 so the cancelation property holds and we get  a^{d\varphi(\varphi(n))}\equiv1\bmod{n} which isn't always true.

    Edit: I read your question wrong... hold on for a bit
    Last edited by chiph588@; June 2nd 2010 at 09:23 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    715
    We can't say any a coprime to n .

    If  a is the primitive element , we must have exactly

     a^{\varphi(n)} = 1 .

    However ,  \varphi(\varphi(n) ) < \varphi(n) so \varphi(\varphi(n) ) cannot contain  \varphi(n) and we have  a^{ \varphi(\varphi(n) ) } \neq 1

    For example ,

     8^{ \varphi(\varphi(17)) } = 8^8  \equiv 1 \bmod{17}

    but  3^8 \equiv -1 \bmod{17}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by chiph588@ View Post
     b^c \bmod{\varphi(\varphi(n))} = b^c+d\varphi(\varphi(n)) for some  d

     a^{b^c+d\varphi(\varphi(n))}=a^{b^c}a^{d\varphi(\v  arphi(n))}\equiv a^{b^c} \bmod{n}

    Since  (a,n)=1\implies (a^{b^c},n)=1 so the cancelation property holds and we get  a^{d\varphi(\varphi(n))}\equiv1\bmod{n} which isn't always true.

    Edit: I read your question wrong... hold on for a bit
     c \bmod{\varphi(\varphi(n))} = c+d\varphi(\varphi(n)) for some  d

    So  a^{b^{c+d\varphi(\varphi(n))}} = a^{b^cb^{d\varphi(\varphi(n))}} = \left(a^{b^c}\right)^{d\varphi(\varphi(n))}\equiv a^{b^c}\bmod{n}

    Therefore we require  d\varphi(\varphi(n))\equiv1\bmod{\phi(n)} or  a^{b^c}\equiv1\bmod{n} ; this last part is trivial though.

    When  \varphi(n)\neq2 we have  2\mid(d\varphi(\varphi(n)),\varphi(n)) so the above line can't have a solution.

    If  \varphi(n)=2\implies n=3 , so we want to solve  d\equiv1\bmod{2} which we can do. Note in this case  d can be even too. This is because if  b=1 the exponent doesn't matter and if  b=2 then  \varphi(n)\mid b^c . I'd consider  n=3 to be a trivial case.

    So in summary there is only one case where you're statement holds, namely  n=3 .

    Edit: This post is also wrong. See below.
    Last edited by chiph588@; June 2nd 2010 at 10:18 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    I don't really see where chiph588@ and simplependulum are coming from, but it seems to me that what you wrote is completely valid as long as \text{gcd}(b, \varphi(n))=1. We are merely applying Euler's theorem twice.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by undefined View Post
    I don't really see where chiph588@ and simplependulum are coming from, but it seems to me that what you wrote is completely valid as long as \text{gcd}(b, \varphi(n))=1. We are merely applying Euler's theorem twice.
    Again, I made a huge mistake in my last post. My mistake came from saying  a^{b^cb^{d\varphi(\varphi(n))}} = \left(a^{b^c}\right)^{d\varphi(\varphi(n))} . It should read  a^{b^cb^{d\varphi(\varphi(n))}} = \left(a^{b^c}\right)^{b^{d\varphi(\varphi(n))}}

    I then said we need  d\varphi(\varphi(n))\equiv1\bmod{\phi(n)} but what we actually need is  b^{d\varphi(\varphi(n))}\equiv1\bmod{\phi(n)}

    which like you said requires  (b,\phi(n))=1

    Two huge mistakes on one thread, how embarassing!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Haha looks like my question spilled a lot of virtual ink.

    Thank you for your replies, with your help I managed to set up something that I can prove. Here's a nice theorem (don't know if it already exists ?) :

    Let \varphi_0{(n)} = n, \varphi_1{(n)} = \varphi{(n)}, \varphi_2{(n)} = \varphi{(\varphi{(n)})}, ...

    Assume a_0, a_1, \cdots, a_n are relative numbers with the property that \gcd{(a_i, \varphi_i{(n)})} = 1 for all 0 \leqslant i \leqslant n. Then the following holds :

    a_0^{\left ( a_1^{\left ( a_2^{\left ( a_3^{\cdots^{( a_n + 1)}  - 1} \right )} - 1 \right )} - 1 \right )} - 1 \equiv 0 \pmod{n}

    I will post the proof in some time. I do have it but it needs ... editing. It's quite simple, based on substituting zeroes modulo various \varphi_i{(n)}.

    Coming back to the original question, it is indeed a matter of greatest common divisors. For instance, I can hopefully prove the original statement using a variation of my general proof:

    a^{\left ( b^{(c + \varphi{(\varphi{(n)})})} \right )} \equiv a^{\left ( b^c \right )} \pmod{n}

    Due to Euler's Theorem this may only work if \gcd{(a, n)} = 1. And again due to Euler's Theorem, we can write the following congruence from the statement :

    b^{(c + \varphi{(\varphi{(n)})})} \equiv b^c \pmod{\varphi{(n)}}.

    This, again, can only work if \gcd{(b, \varphi{(n)})} = 1. Reapplying Euler's Theorem again the following congruence is obtained :

    c + \varphi{(\varphi{(n)})} \equiv c \pmod{\varphi{(\varphi{(n)})}}

    With does hold for any c. Thus the original statement holds iff \gcd{(a, n)} = 1 and \gcd{(b, \varphi{(n)})} = 1.

    Is this a valid proof ?
    Last edited by Bacterius; June 3rd 2010 at 02:42 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bacterius View Post
    Haha looks like my question spilled a lot of virtual ink.

    Thank you for your replies, with your help I managed to set up something that I can prove. Here's a nice theorem (don't know if it already exists ?) :

    Let \varphi_0{(n)} = n, img.top {vertical-align:15%;} \varphi_1{(n)} = \varphi{(n)}" alt=" \varphi_1{(n)} = \varphi{(n)}" />, \varphi_2{(n)} = \varphi{(\varphi{(n)})}, ...

    Assume a_0, a_1, \cdots, a_n are relative numbers with the property that \gcd{(a_i, \varphi_i{(n)})} = 1 for all 0 \leqslant i \leqslant n. Then the following holds :

    a_0^{\left ( a_1^{\left ( a_2^{\left ( a_3^{\left ( a_4^{\cdots^{( a_n + 1)}} - 1 \right )} - 1 \right )} - 1 \right )} - 1 \right )} - 1 \equiv 0 \pmod{n}

    I will post the proof in some time. I do have it but it needs ... editing. It's quite simple, based on substituting zeroes modulo various \varphi_i{(n)}.
    I believe if you can show  \varphi_{n-1}(n)=1 \;\forall\; n then the proof is easy. What's your version of the proof?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    This whole thread has relevance for what I'd consider a fun/beautiful problem over at Project Euler: (spoiler box contains link)

    Spoiler:

    I don't like giving hints that are too substantial or giving away answers, but it's such a nice tie-in I couldn't resist. Anyway, knowing that this thread is relevant doesn't make it obvious how to solve.

    Just to be extra safe, I put it in a spoiler box, so that if you want, you'll only know it has relevance to one of the problems there, but not which one.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by chiph588@ View Post
    I believe if you can show  \varphi_{n-1}(n)=1 \;\forall\; n then the proof is easy. What's your version of the proof?
    You guys are so prompt at answering

    My proof looks like this :

    Quote Originally Posted by Proof draft
    Let : a_i^{b_i} \equiv 1 \pmod{\varphi_i{(n)}} for any b_i. Euler's Theorem tells us that \gcd{(a_i, \varphi_i{(n)})} = 1 for any 0 \leqslant i \leqslant n - 1 (these become the conditions for the statement).

    Then b_i \equiv 0 \pmod{\varphi_{i + 1}{(n)}} again due to Euler's Theorem.

    But the original statement is equivalent to saying that b_i = a_{i + 1}^{b^{i + 1}} - 1. Substituting :

    a_{i + 1}^{b^{i + 1}} - 1 \equiv 0 \pmod{\varphi_{i + 1}{(n)}}

    Or :

    a_{i + 1}^{b^{i + 1}} \equiv 1 \pmod{\varphi_{i + 1}{(n)}}

    Which is equivalent to what has been assumed as a condition.
    The same argument is valid for any 0 \leqslant i \leqslant n - 1. Thus the statement holds assuming the original conditions.
    I know this needs editing but I'm pretty sure it is a valid proof, probably formulated in a twisted way though. What do you think ?

    Thanks for the link undefined, I'm bookmarking it.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bacterius View Post
    You guys are so prompt at answering

    My proof looks like this :



    I know this needs editing but I'm pretty sure it is a valid proof, probably formulated in a twisted way though. What do you think ?

    Thanks for the link undefined, I'm bookmarking it.
    I think with a little more work this would be valid, but I think my way would be a lot less complicated:

    We know  \varphi_{n-1}(n)=1\implies a_{n-1}=1 , so  a_{n-1}^{a_n+1}-1=0 . Thus  a_{n-2}^0-1=0 and we see this pattern will trickle down to  a_0 . So we eventually get  a_0^0-1 .
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by chiph588@ View Post
    I think with a little more work this would be valid, but I think my way would be a lot less complicated:

    We know  \varphi_{n-1}(n)=1\implies a_{n-1}=1 , so  a_{n-1}^{a_n+1}-1=0 . Thus  a_{n-2}^0-1=0 and we see this pattern will trickle down to  a_0 . So we eventually get  a_0^0-1 .
    Clever !
    I didn't think of it this way. Indeed, it is way simpler to understand (and to write in Latex as well )

    Thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 5th 2010, 02:04 AM
  2. Euler Totient Function
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: June 3rd 2010, 06:38 PM
  3. Euler totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 10:33 AM
  4. Euler's Totient Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2009, 08:16 PM
  5. Euler totient function
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 25th 2007, 08:10 AM

Search Tags


/mathhelpforum @mathhelpforum