Finding the mod of large numbers

[valianth1]

Homework Statement

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

Homework 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

The Attempt at a Solution

 

[Dick]

Homework Statement

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

Homework 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

The Attempt at a Solution

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

 

[valianth1]

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

 

[Dick]

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]

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]

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]

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?