Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number theory problem about Fermat 's little theorem

  1. Feb 11, 2012 #1
    1. The problem statement, all variables and given/known data

    let n be an integer . Prove the congruence below.
    n^21 [itex]\equiv[/itex] n mod 30

    2. Relevant equations

    n^7 [itex]\equiv[/itex] n mod 42

    n^13 [itex]\equiv[/itex] n mod 2730

    3. The attempt at a solution

    to prove 30| n^21-n,it suffices to show 2|n^21-n,3|n^21-n,5|n^21-n
    and how to prove them?
     
  2. jcsd
  3. Feb 11, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    2|n^21-n should be pretty easy. Just think about odd and even. To start on the second one n^3=n mod 3. n^(21)=(n^3)^7. Now keep going.
     
  4. Feb 11, 2012 #3
    then n^21-n = n(n^20-1), suppose n is even , then 2|n^21-n
    if n is odd, n^20 is odd, so n^20-1 is even;

    to 3, it means n^21=(n^3)^7=n^7=(n^3)^2*n
    then how is the next to prove 3|n(n^20-1)
     
  5. Feb 11, 2012 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You are almost there with this line, "to 3, it means n^21=(n^3)^7=n^7=(n^3)^2*n". Think about it a little more and you will get it.
     
  6. Feb 12, 2012 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Keeping thinking n^3=n, n^3=n.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook