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

    valianth1

    User Avatar

    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
     
    valianth1, Nov 5, 2011
  2. jcsd
    Phys.org - latest science and technology news stories on Phys.org
  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.
     
    Dick, Nov 5, 2011
  4. Nov 5, 2011 #3

    valianth1

    User Avatar

    16(mod 17) = -1 and 18(mod 17) = 1, how do I go from here?
     
    valianth1, Nov 5, 2011
  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
    Dick, Nov 5, 2011
  6. Nov 6, 2011 #5

    valianth1

    User Avatar

    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
     
    valianth1, Nov 6, 2011
  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.
     
    I like Serena, Nov 6, 2011
  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?
     
    Dick, Nov 6, 2011
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Finding the mod of large numbers

  1. Solving large #s raised to a large # with the mod function (Replies: 1)

  2. Help with factor large numbers (Replies: 6)

  3. Large numbers (Replies: 4)

  4. Finding the number of arrangements (Replies: 10)

  5. Finding The Number of People At A Party (Replies: 6)

Loading...