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: Finding the mod of large numbers

  1. Nov 5, 2011 #1
    1. The problem statement, all variables and given/known data

    Evaluate (16^1000 - 18^2000)(mod 17)


    2. Relevant equations

    I'm not sure how to go about doing this, but I realise it has something to do with the pattern from the last digit obtained from the 2 large numbers


    3. The attempt at a solution
     
  2. jcsd
  3. Nov 5, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That's really not a great realization. I would think about what 16 and 18 are mod 17.
     
  4. Nov 5, 2011 #3
    16(mod 17) = -1 and 18(mod 17) = 1, how do I go from here?
     
  5. Nov 5, 2011 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    What's (-1)^1000-1^2000? (x mod 17)^n mod 17=(x^n) mod 17. Right?
     
    Last edited: Nov 5, 2011
  6. Nov 6, 2011 #5
    Turns out 16(mod17) is 16, so how would I go about calculating 16^1000 seeing that the exam does not permit calculators? So would the solution be 16^1000 - 1^2000? So is the solution 15? Because using the calculator returns 0 which I don't think is right
     
  7. Nov 6, 2011 #6

    I like Serena

    User Avatar
    Homework Helper

    How did you get 16(mod17) to be 16?

    Consider that (-1)1000 = 1.


    Btw, since 17 is prime you can also apply Fermat's little theorem:
    For any prime p: ap (mod p) = a

    Rewrite 161000 as 1617k+r=(1617)k16r.
     
  8. Nov 6, 2011 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    16 and (-1) are congruent mod 17 since they differ by 17. So (-1)^1000=16^1000 mod 17. You can use either form in your calculation. Which one makes it easy?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook