Results 1 to 5 of 5

Math Help - Exponents and Fermat's Little Theorem

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    3

    Exponents and Fermat's Little Theorem

    I am attempting to solve two problems. The first is to compute, in linear time, a^(b^c) mod p. The hint is to use Fermat's Little Theorem to simplify the problem.

    The second problem is to simplify 5^596 mod 599.

    These problems seem so easy, and yet their solutions esacape me.

    In the first problem, I cannot simplify a^(b^c) mod p using Fermat's Little Theorem. Somehow I need to manipulate the problem to the form of:

    ( a^(p-1) * a^(p-1) * ... * a^x) mod p

    Can anyone offer suggestions or guidance on these two problems?

    Thank you in advance for your help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Mar 2010
    Posts
    3
    In regards to the simplification problem (5^596 mod 599): I know the answer is 24, and I also know I can simplify 5^596 to:

    5^596
    = 5^(598-2)
    = 5^598 * 5^-2

    The problem (5^598 * 5^-2) mod 599 becomes (1* 5^-2) mod 599. But this simplified problem does not equal 24. Does anyone know what I'm doing wrong?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,506
    Thanks
    765
    But this simplified problem does not equal 24.
    Yes, it does. Find 5^{-1}\pmod{599} and then find its square.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2010
    Posts
    3
    I'm sorry, but I still don't see how this works. 5^-1 mod 599 equals 120.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,506
    Thanks
    765
    5^-1 mod 599 equals 120.
    And 120^2=14400\equiv24\pmod{599} (can be checked by direct calculation).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermatís Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 27th 2011, 06:52 PM
  2. Fermat's Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 3rd 2011, 04:58 PM
  3. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  4. Fermat's little theorem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 17th 2009, 06:28 AM
  5. Not Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 8th 2008, 10:39 PM

Search Tags


/mathhelpforum @mathhelpforum