Results 1 to 11 of 11

Math Help - Fermat's Little Theorem

  1. #1
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169

    Fermat's Little Theorem

    I am having trouble knowing where to start to use Fermat's Little Theorem to find the least residue of 5^10 (mod 11). Could you please offer some guidance? Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member craig's Avatar
    Joined
    Apr 2008
    Posts
    748
    Thanks
    1
    Awards
    1
    Fermat's Little Theorem states that:

    a^p = a (mod p) where p is a prime number.

    Dividing both sides by a, we get:

    a^{p-1} = 1 (mod p)

    Compare this to your question, what do you notice?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169
    That worked out nicely for my first simple example. Thanks! But when I encounter a situation like 5^12(mod 11), I am back to square one. Or do I restate 5^12 as 5^10*5^2 (mod 11)? Would this be congruent to 25 * 1(mod 11)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169
    Oops--duh--5^10 * 5^2 (mod 11) == 5^2 * 1(mod 11) == 3(mod 11). Right?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Hello, you want to solve this for x :
    5^{12} \equiv x \pmod{11}

    By Fermat's Little Theorem, we are left with 5^2 \equiv x \pmod{11}. Now, 5^2 = 25, and 25 \equiv 3 \pmod{11}, so 5^{12} \equiv 3 \pmod{11}.

    Basically, you want to simplify the difficult calculation 5^{12} until the remaining operations can be done mentally or easily on a calculator. It is up to you to decide whether 5^2 can be calculated manually.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member craig's Avatar
    Joined
    Apr 2008
    Posts
    748
    Thanks
    1
    Awards
    1
    Quote Originally Posted by tarheelborn View Post
    That worked out nicely for my first simple example. Thanks! But when I encounter a situation like 5^12(mod 11), I am back to square one. Or do I restate 5^12 as 5^10*5^2 (mod 11)? Would this be congruent to 25 * 1(mod 11)?
    Yes basically what Bacterius said. You need to simplify as much as possible and then work from there.

    Remember though that Fermat's little Theorem only works if p is a prime number.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Remember though that Fermat's little Theorem only works if p is a prime number.
    Note that Fermat's Little Theorem is simply one particular case of Euler's Theorem :

    a^{\varphi{(m)}} \equiv 1 \pmod{m} iff gcd(a, m) = 1. \varphi{(m)} is the Euler totient function, that is, the quantity of numbers that are coprime with m. Coincidentally, if m is prime, then \varphi{(m)} = m - 1
    Last edited by Bacterius; February 24th 2010 at 07:39 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bacterius View Post
    Ironically, if m is prime, then \varphi{(m)} = m - 1
    I don't think "ironically" is the correct word here. It is coincidental that this is the case.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Effectively, just looked it up on the dictionary
    It's quite hard to find the words sometimes ...
    Forgive my english
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bacterius View Post
    Effectively, just looked it up on the dictionary
    It's quite hard to find the words sometimes ...
    Forgive my english
    Don't be sorry! You're a very contributive member on MHF! You didn't say anything wrong...it was just a note
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    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, 07:52 PM
  2. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  3. Fermat's Little Theorem 2
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: October 7th 2008, 07:47 PM
  4. Fermat Little Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 4th 2008, 01:40 PM
  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