Results 1 to 6 of 6

Math Help - fermat,euler,or CRT?

  1. #1
    Junior Member
    Joined
    Dec 2007
    From
    University of California, Berkeley
    Posts
    48

    fermat,euler,or CRT?

    .
    >
    Last edited by yellow4321; March 6th 2008 at 06:28 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Dec 2007
    From
    University of California, Berkeley
    Posts
    48
    .
    >
    .
    Last edited by yellow4321; March 6th 2008 at 06:28 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Well 37 is prime, thus: 7^{36}\equiv{1}(\bmod.37) (Fermat's little theorem)

    7^{25}\equiv{z}(\bmod.36) with 0\leq{z}<36

    Thus: 7^{7^{25}}=7^{36k+z}\equiv{7^{z}}(\bmod.37) where k is a natural number

    We shall now find z

    Note that \phi(36)=12 thus by Euler's Theorem: 7^{12}\equiv{1}(\bmod.36) and (squaring) 7^{24}\equiv{1}(\bmod.36)

    So: 7^{25}\equiv{7}(\bmod.36) and z=7

    We finally get that: 7^{7^{25}}\equiv{7^7}(\bmod.37)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    For the order of 17, you might be tempted to try Euler's theorem, but it will not give you an answer. However it will let you narrow your search. Then you can kill the problem by case wise analysis.
    What I mean is:
    Indeed 17^{\phi(27)} \equiv 1 \mod 27 \Rightarrow 17^{18} \equiv 1 \mod 27
    But this only says the order divides 18. So it can be any element from the set {2,3,6,9,18}.
    Try all these possibilities in the increasing order and you will get 6 as the answer.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Dec 2007
    From
    University of California, Berkeley
    Posts
    48
    pure genius
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Sorry about my first post. Doubt if it was much help. I was in a hurry and got to thinking of someting else. Anyway:

    Here's one way I got to looking at.

    There are 9 non zero modulo 37 residues. So we must figure out where 7^{25} lies in this repeating chain of remainders.

    7^{0}\equiv{1}(mod \;\ 37)

    7^{1}\equiv{7}(mod \;\ 37)

    7^{2}\equiv{12}(mod \;\ 37)

    7^{3}\equiv{10}(mod \;\ 37)

    7^{4}\equiv{33}(mod \;\ 37)

    7^{5}\equiv{9}(mod \;\ 37)

    7^{6}\equiv{26}(mod \;\ 37)

    7^{7}\equiv{34}(mod \;\ 37)

    7^{8}\equiv{16}(mod \;\ 37)

    Then they repeat.

    But, 7^{25}\equiv{7}(mod \;\ 9)

    That means 7^{25} is 7 more than a multiple of 9.

    So, we count up the residues and see we light at a remainder of 34.

    Another thing we may be able to do is since 7^{9}\equiv{1}(mod \;\ 37), we can break 7^{25} into as many powers of 7^{9} as possible.

    7^{25}=7^{7}\cdot{7^{18}}=7^{7}(7^{9})^{2}=7^{7}(1  )^{2}=7^{7}\equiv{34}(mod \;\ 37)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  2. Working with mod p (Euler's and Fermat's Theorem)
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 23rd 2010, 12:22 AM
  3. Replies: 0
    Last Post: February 20th 2010, 09:26 AM
  4. Replies: 0
    Last Post: September 17th 2009, 07:44 PM
  5. prove by fermat-euler
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 11th 2008, 08:44 AM

Search Tags


/mathhelpforum @mathhelpforum