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!

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




Similar Discussions: Finding the mod of large numbers
  1. Large numbers (Replies: 4)

Loading...