Finding the mod of large numbers

valianth1 · Nov 5, 2011

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

Dick · Nov 5, 2011

valianth1 said: ↑

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

That's really not a great realization. I would think about what 16 and 18 are mod 17.

valianth1 · Nov 5, 2011

16(mod 17) = -1 and 18(mod 17) = 1, how do I go from here?

Dick · Nov 5, 2011

valianth1 said: ↑

16(mod 17) = -1 and 18(mod 17) = 1, how do I go from here?

What's (-1)^1000-1^2000? (x mod 17)^n mod 17=(x^n) mod 17. Right?

valianth1 · Nov 6, 2011

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

I like Serena · Nov 6, 2011

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

Consider that (-1)¹⁰⁰⁰ = 1.

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

Rewrite 16¹⁰⁰⁰ as 16^17k+r=(16¹⁷)^k16^r.

Dick · Nov 6, 2011

valianth1 said: ↑

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

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?