Results 1 to 3 of 3

Math Help - Fermat's Little Theorem

  1. #1
    Newbie
    Joined
    Apr 2011
    Posts
    2

    Fermat's Little Theorem

    Hi all,
    I have just joined this forum hoping to get some help.
    I have just recently started playing with Number Theory and I am trying to
    get my head around Modular Arithmatic. So I came across Fermat's Little Theorem,
    which says that a^p = a (mod p). Why does this seem to work with some values but not with others? 9^7 = 2 (mod 7) or 12^5 = 2 (mod 5) or 8^5 = 3 (mod 5). Am I missing something here? The other form of the theorem a^(p-1) = 1 (mod p) seems to work just fine. Yes and I do know that the values have to be coprime. Can anyone help me get this?
    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Rhymes with Orange Chris L T521's Avatar
    Joined
    May 2008
    From
    Chicago, IL
    Posts
    2,844
    Thanks
    3
    Quote Originally Posted by zophas View Post
    Hi all,
    I have just joined this forum hoping to get some help.
    I have just recently started playing with Number Theory and I am trying to
    get my head around Modular Arithmatic. So I came across Fermat's Little Theorem,
    which says that a^p = a (mod p). Why does this seem to work with some values but not with others? 9^7 = 2 (mod 7) or 12^5 = 2 (mod 5) or 8^5 = 3 (mod 5). Am I missing something here? The other form of the theorem a^(p-1) = 1 (mod p) seems to work just fine. Yes and I do know that the values have to be coprime. Can anyone help me get this?
    Thanks.
    Its all fine..but note that a\in\{0,1,2,\ldots,p-1\} should be true. In other words, a should be a value in the appropriate residue system you're working with.

    So in your examples, observe that 9\equiv 2\pmod{7}, 12\equiv 2\pmod 5 and 8\equiv 3\pmod{5}. (*)

    Thus, it follows that 9^7\equiv \boxed{2^7\equiv 2\pmod{7}}, 12^5\equiv \boxed{2^5\equiv 2\pmod{5}} and 8^5\equiv\boxed{3^5\equiv 3\pmod{5}}.

    I hope this clarifies things!

    EDIT: You could also observe that

    9^7\equiv 2\pmod{7} \implies 9^7 \equiv 9\pmod{7} by what I said in (*).

    Similarly, we also see that 12^5\equiv 2\pmod{5}\implies 12^5\equiv 12\pmod{5} and 8^5\equiv 3\pmod{5}\implies 8^5\equiv 8\pmod{5}.

    The moral of the story: Fermat's Little Theorem holds as long as \gcd(a,p)=1. But most solutions will be simplified so that they lie within the residue system \{0,1,2,\ldots,p-1\}. So I would recommend simplifying the expression first and then apply Fermat's little theorem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2011
    Posts
    2
    Thank you very much, Chris
    I can see that I need a Modular Arithetic for Dummies book.
    Glad I found this forum.
    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. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 11th 2010, 09:43 AM
  3. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 19th 2009, 10:47 PM
  4. Fermat's Little Theorem Help [again]
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 28th 2008, 09:15 AM
  5. Help with Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 3rd 2008, 05:14 PM

Search Tags


/mathhelpforum @mathhelpforum