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: Least positive integer, modular problem HELP!

  1. Mar 25, 2012 #1
    1. The problem statement, all variables and given/known data

    find the least positive integer n for which 5[itex]^{n}[/itex] [itex]\equiv[/itex] 1 (mod17) or 5[itex]^{n}[/itex] [itex]\equiv[/itex] -1 (mod 17)



    2. Relevant equations



    3. The attempt at a solution

    I really dont understand and method to doing these problems as I cant use a calculator and I can only work out powers maybe up to 4 or 5 (depending) in my head... the answer says its 8 but how would I work out in my head 5[itex]^{8}[/itex] +1 and then know it was divisible by 17???

    There must be an easier way,,, please help!
     
  2. jcsd
  3. Mar 26, 2012 #2
    The trick is to keep reducing mod 17 as you go. So:

    5^2 = 25 = 8 (mod 17)
    5^4 = 8 * 8 = 64 = 13 = -4 (mod 17)
    5^8 = (-4) * (-4) = 16 = -1 (mod 17)

    If you wanted you could have computed 5^2, 5^3, 5^4, 5^5, ... the same way. But note that 5^16 = 1 (mod 17) by Fermat's little theorem. So if 5^n = 1 or 5^n = -1, n must divide 16. So we only have to check n = 2, 4, and 8.
     
  4. Mar 26, 2012 #3
    Thanks a bunch steve that cleared things up heaps!!!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook