Results 1 to 2 of 2

Math Help - Fermat's little theorem

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    12

    Red face Fermat's little theorem

    Using Fermat's little theorem, how do I calculate

    26^23 mod 51

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517

    can't use it directly

    I don't see a good way to apply fermat's little theorem directly; however, there is a relatively easy fix.

    51=3*17 We need only solve this mod 3 and mod 17 and then the chinese remainder theorem gives you the unique solution mod 51.

    It is much easier to solve this equation here. 26 \cong 2 \cong -1 (mod 3) \Rightarrow 26^{23} \cong -1^{23} \cong -1 \cong 2 (mod 3)

    Similarly 26 \cong 9 (mod 17) You can reduce mod 17 to see what 9^{23} \cong 9^{16+7} \cong 9^{16}9^7 \cong 1*9^7 is mod 17, it is easy to note 9^2 is -4 and so 9^4=16=-1 so the solution is 2 mod 17.

    So you just need to solve the following congruence.
    x\cong 2 (mod 3)
    x \cong 2 (mod 17)

    Just use the CRT like I mentioned to get this solution, there is a really really obvious answer to this case by inspection, lol, but in general this is how you would do it in case you have to do something similar to this but doesn't work out quite so nice.
    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. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  3. Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 18th 2010, 01:33 AM
  4. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 19th 2009, 09:47 PM
  5. Fermat's Little Theorem Help [again]
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 28th 2008, 08:15 AM

Search Tags


/mathhelpforum @mathhelpforum