Results 1 to 5 of 5

Math Help - Fermat's little theorem

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    3

    Fermat's little theorem

    Need help with computing the following by using Fermat's little theorem. I've been reading in advance and would like to wrap my head around this before the actual lesson, but I've found it trickier than expected. Any help is welcome!

    10^117 (mod 7)
    (17)^145 (mod 11)
    3^302 (mod 5)
    5^2003 (mod 13)
    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,

    First, you can simplify :

    10^{117}\equiv 3^{117} (\bmod 7)
    Then Fermat's little theorem implies that 3^6\equiv (\bmod 7)
    Since 117=6\times 19+3, you have :
    3^{117}=(3^6)^{19}\cdot 3^3 \equiv 1^{19}\cdot 27 (\bmod 7)
    And hence 10^{117}\equiv 6(\bmod 7)

    It's the same for the others. identity the number b such that a^b\equiv 1(\bmod n), and then write the Euclidean division of the exponent by b.

    For the second one, it simplifies also as 6^{145} (\bmod 11)
    Spoiler:
    By Fermat's little theorem, we know that 6^{10}\equiv 1(\bmod 11)
    Since 145=14\times 10+5, we have :
    6^{145}\equiv6^5 (\bmod 11)

    And then, it's pretty awful to calculate 6^5, so note that 6^2=36\equiv 3(\bmod 11)

    So 6^5=6^2 \cdot 6\equiv 3^2 \cdot 6 (\bmod 11) \equiv 1 (\bmod 11)


    Does it look clear to you ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    3
    Quote Originally Posted by Moo View Post
    Hello,

    First, you can simplify :

    10^{117}\equiv 3^{117} (\bmod 7)
    Then Fermat's little theorem implies that 3^6\equiv (\bmod 7)
    Since 117=6\times 19+3, you have :
    3^{117}=(3^6)^{19}\cdot 3^3 \equiv 1^{19}\cdot 27 (\bmod 7)
    And hence 10^{117}\equiv 6(\bmod 7)

    Does it look clear to you ?
    Thanks for your help. I think I am understanding it now, but how did it become congruent to 1^19 . 27(mod 7)? And for the second question, how did 6^10 become congruent to 1(mod11)? Sorry, it's just that I am quite ill now, it usually takes me faster to grasp things. Thanks again
    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 djsilva View Post
    Thanks for your help. I think I am understanding it now, but how did it become congruent to 1^19 . 27(mod 7)?
    Remember these properties :
    a\equiv b(\bmod n)\Rightarrow \begin{array}{ll} a^c\equiv b^c(\bmod n) \\ ac\equiv bc(\bmod n)\end{array}

    Because 3^6\equiv 1(\bmod 7), it follows that (3^6)^{19}\equiv 1 (\bmod 7) (or 1^{19} if you need this step)
    Then 3^{117}=(3^6)^{19} \cdot 3^3 \equiv 1\cdot 3^3 (\bmod 7)
    and since 3^3=27...

    If you don't understand why 3^{117}=(3^6)^{19}\cdot 3^3, I'll refer you to the properties of exponents : a^{bc}=(a^b)^c=(a^c)^b and a^{b+c}=a^b\cdot a^c


    And for the second question, how did 6^10 become congruent to 1(mod11)?
    This is Fermat's little theorem ^^

    Sorry, it's just that I am quite ill now, it usually takes me faster to grasp things. Thanks again
    No problem. My explanations aren't the clearest possible either...


    Can you try to do the last 2 ones ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2009
    Posts
    3
    Ah, thanks, it is better now. I'll be able to solve the rest now
    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