Results 1 to 9 of 9

Math Help - Euler's Theorem

  1. #1
    Junior Member
    Joined
    Feb 2007
    Posts
    70

    Euler's Theorem

    I'm supposed to prove that a^{37} \equiv a(mod\ 1729) for any integer a using Euler's theorem. I'm trying to first prove it under the assumption that gcd(a, 1729)=1, which allows me to apply Euler's theorem. In this case, I showed that a^{\phi(1729)}=a^{1296}=(a^{36})^{36} \equiv 1(mod\ 1796). What I want to do is get from here to a^{36} \equiv 1(mod\ 1796) so I can multiply both sides by a and get the result. However, I'm not sure how to fill in that gap. Is there some theorem I can use? Or am I going about this in the wrong way?

    Also, I'm not sure how to handle the case where a and 1729 are not relatively prime. Any help there would be appreciated as well.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Also, I'm not sure how to handle the case where a and 1729 are not relatively prime.
    If a is not coprime with 1729, this means that a doesn't belong to the invertible group of Z/1729Z. So there doesn't exist b such as a^b \equiv 1 [1729] \Longrightarrow a^{b+1} \equiv a [1729]
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2007
    Posts
    70
    Thanks for the reply, but this is for an elementary number theory course. I can't use any group theory. Is there a different way I can handle that case?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by spoon737 View Post
    Thanks for the reply, but this is for an elementary number theory course. I can't use any group theory. Is there a different way I can handle that case?
    Hm...

    Let a be a non-coprime number with 1729. Therefore, there is a common factor d, different from 1.

    Is there b such as :
    a^b \equiv 1 [1729] ?

    If so, we know that a^b-1 is a multiple of 1729 : a^b-1=1729k, k \in \mathbb{Z}

    a^b=1729k+1

    Since d divides a, it divides a^b. And it divides 1729 too. So it has to divide 1 too, which is not possible unless d=1 -> contradiction.

    Is it better this way ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2007
    Posts
    70
    Okay, that's definitely within the scope of the material I know, but I'm not sure how it relates to what I'm trying to prove. I need to show that a^{37} \equiv a(mod\ 1729) for any integer a. The last part of my original post is asking how to show this when a and 1729 aren't coprime. Perhaps I'm just not seeing the connection?

    Also, any help with the first part of my post would be greatly appreciated as well.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by spoon737 View Post
    Okay, that's definitely within the scope of the material I know, but I'm not sure how it relates to what I'm trying to prove. I need to show that a^{37} \equiv a(mod\ 1729) for any integer a. The last part of my original post is asking how to show this when a and 1729 aren't coprime. Perhaps I'm just not seeing the connection?
    I think I showed you couldn't find any power of a such as a^b \equiv a [1729] if a and 1729 aren't coprime.

    I'm quite tired and I can't help with the first part, sorry...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Feb 2007
    Posts
    70
    Hmm, that's strange. According to my book, it should be true for all integers, whether a and 1729 are coprime or not. I just thought it would be easiest to prove it in both cases.

    Thanks for your input, though, I really appreciate the help.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    1729 = 7\cdot 13\cdot 19.
    Let \gcd(a,1729)=1 then the maximal order of a mod 1729 is \text{lcm}(\phi(7),\phi(13),\phi(19)) = \text{lcm}(6,12,18)=36.
    Also \text{ord}(a) | \phi(1729) = 36^2. Combining these two results we get that \text{ord}(a) | 36.
    This immediately tells us that a^{36} \equiv 1(\bmod 1729).
    Multiply both sides by a: a^{37}\equiv a(\bmod 1729).

    The next step is to argue that: 7^{36}\equiv 1(\bmod  13\cdot 19), 13^{36}\equiv 1(\bmod 7\cdot 19), 19^{36}\equiv 1(\bmod 7\cdot 13).
    We will prove the first case, the other two are similar.
    Note \gcd(7,13\cdot 19)=1 and maximal order of a mod 13\cdot 19 is \text{lcm}(\phi(13),\phi(19)) = 36.
    Using a similar argument as in the first paragraph we can get 7^{36}\equiv 1(\bmod 13\cdot 19).
    This tells us that: 7^{37}\equiv 7, 13^{37}\equiv 13, 19^{37}\equiv 19(\bmod 1729).

    Say that \gcd(a,1729)\not = 1 this means 7|a or 13|a or 17|a.
    Say that 7|a but not the other factors, i.e. a=7b and \gcd(b,1729) = 1.
    Then, a^{37} \equiv a (\bmod 1729) \implies 7^{37}b^{37}\equiv 7 b(\bmod 1729).
    But b^{37}\equiv b(\bmod 1729) by above argument.
    Thus, we are left with 7^{37}\equiv 7(\bmod 1729).
    This is of course true.
    The same argument when 13|a and 19|a.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Moo View Post
    Hello,



    If a is not coprime with 1729, this means that a doesn't belong to the invertible group of Z/1729Z. So there doesn't exist b such as a^b \equiv 1 [1729] \Longrightarrow a^{b+1} \equiv a [1729]
    Quote Originally Posted by Moo View Post
    Hm...

    Let a be a non-coprime number with 1729. Therefore, there is a common factor d, different from 1.

    Is there b such as :
    a^b \equiv 1 [1729] ?

    If so, we know that a^b-1 is a multiple of 1729 : a^b-1=1729k, k \in \mathbb{Z}

    a^b=1729k+1

    Since d divides a, it divides a^b. And it divides 1729 too. So it has to divide 1 too, which is not possible unless d=1 -> contradiction.

    Is it better this way ?
    Here is another way.
    Say that a^{36}\equiv 1(\bmod 1729). This means \gcd(a^{36},1729) = \gcd(1,1729) = 1 (because they are the same under the same modulos). Thus, \gcd(a,1729)\not = 1 which is a problem.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  2. How to use Euler's theorem ?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 7th 2010, 09:04 AM
  3. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 5th 2009, 09:07 AM
  4. Euler's Theorem
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: November 19th 2008, 05:47 AM
  5. Euler's theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 25th 2007, 12:53 PM

Search Tags


/mathhelpforum @mathhelpforum