1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fermat's little theorem

  1. Mar 18, 2009 #1
    1. The problem statement, all variables and given/known data

    From fermat's little theorem deduce that when p is prime,

    n^p is equivalent to n (mod p)

    for all integers n.

    2. Relevant equations



    3. The attempt at a solution

    I know from Fermat's Little Theorem that ,

    n^(p-1) is equivalent to 1 (mod p),

    but i don't know how to use it for this particular question.
     
  2. jcsd
  3. Mar 18, 2009 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If a is equivalent to b mod(p) then c*a is equivalent to c*b mod(p). What might be a good choice for c in your problem?
     
  4. Mar 18, 2009 #3
    ok, so in my question, c=n ?
    So by dividing by n i would get,

    1^p is equiavlent to 1 (mod p)

    How do i reach n^(p-1) on the left hand side?
     
  5. Mar 18, 2009 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    n^p divided by n IS NOT 1^p. PLEASE stop and review algebra with exponents before you try to continue.
     
  6. Mar 18, 2009 #5
    sorry, silly mistake.
    dividing by n would give me,

    n^(p-1) equivalent to 1 (mod p)

    which is fermat's little theorem. so is this all i need to do?
     
  7. Mar 18, 2009 #6
    This is ok if p doesnt divide n, but the question asks me for all integers n.
    So how do i show it's also true for when p divides n?
     
  8. Mar 18, 2009 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You actually want to go the other way. Start with Fermat's little theorem and then go to your conclusion. Multiply by n, you can always do that.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Fermat's little theorem
  1. Fermat Little Theorem? (Replies: 10)

Loading...