Results 1 to 10 of 10

Math Help - Fermat's Little Theorem 2

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    98

    Fermat's Little Theorem 2

    Use Fermat's Little Theorem to compute 29^202 mod 13
    Last edited by bigb; October 7th 2008 at 04:37 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    By Fermat's theorem: a^{12} \equiv 1 \ (\text{mod } 13)

    Note that 29 \equiv 3 \ (\text{mod } 13).

    So: \left(3^{12}\right)^{17} \equiv 1^{17} \ (\text{mod } 13)

    \iff 3^{204} \equiv 1 \ (\text{mod } 13)

    \iff 3^{2} 3^{202} \equiv 1 \ (\text{mod } 13)

    ...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2008
    Posts
    98
    Quote Originally Posted by o_O View Post
    By Fermat's theorem: a^{12} \equiv 1 \ (\text{mod } 13)

    Note that 29 \equiv 3 \ (\text{mod } 13).

    So: \left(3^{12}\right)^{17} \equiv 1^{17} \ (\text{mod } 13)

    \iff 3^{204} \equiv 1 \ (\text{mod } 13)

    \iff 3^{2} 3^{202} \equiv 1 \ (\text{mod } 13)

    ...
    The answer is 81=3mod13..I am messing around with what you did but still cant get the answer. This problem is in my lecture notes but I just cant seem to understand what i wrote.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Following after o_O:

    3^23^{202} \equiv 1 (\mod 13)

    9 \times 3^{202} \equiv 1 (\mod 13)

    27 \times 3^{202} \equiv 3 (\mod 13)

    (13 \times 2 + 1) \times 3^{202} \equiv 3 (\mod 13)

    3^{202} \equiv 3(\mod 13)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2008
    Posts
    98
    Quote Originally Posted by icemanfan View Post
    Following after o_O:

    3^23^{202} \equiv 1 (\mod 13)

    9 \times 3^{202} \equiv 1 (\mod 13)

    27 \times 3^{202} \equiv 3 (\mod 13)

    (13 \times 2 + 1) \times 3^{202} \equiv 3 (\mod 13)

    3^{202} \equiv 3(\mod 13)
    Quick question thou.. What happended to 27 in your answer??
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by bigb View Post
    Quick question thou.. What happended to 27 in your answer??
    It became (13 \times 2 + 1) \equiv 1.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2008
    Posts
    98
    Quote Originally Posted by icemanfan View Post
    It became (13 \times 2 + 1) \equiv 1.
    COmpute 3^302 mod 5

    Would this be right??

    a^4=1mod5
    3=8mod5
    8^4=1mod5
    8^4*76=1^76mod5
    8^2 * 8^302=1mod5
    8^2 * 8^302=-64mod5
    8^302=-1mod5
    8^302=4mod5

    or

    3^4 = 1 (mod 5) by Fermat theorems.
    So (raise to the 75) both sides,
    3^300 = 1 (mod 5)
    Multiply 3^2 both sides,
    3^302 = 3^2 = 9 = 4 (mod 5)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    I would do it the second way
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Sep 2008
    Posts
    98
    Quote Originally Posted by o_O View Post
    I would do it the second way
    It can be done the first way right thou?? If not can the second method be applied to the problem 29^202mod13


    sry for all the dumb questions. I am just trying to learn the material better
    Follow Math Help Forum on Facebook and Google+

  10. #10
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Well it really is the same work but you just did the unnecessary work of showing that 3 is congruent to 8 mod 5.

    And this method WAS used for your problem. Go through it again. The principle is the same. From Fermat's theorem, you have your number to the power of p - 1 is congruent to 1. Raise it as close to the desired power as possible and manipulate it to get what you need.
    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