1. Not finding help here? Sign up for a free 30min 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!

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!!!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Least positive integer, modular problem HELP!
  1. Positive integer proof (Replies: 2)

Loading...