• Support PF! Buy your school textbooks, materials and every day products Here!

Finding the mod of large numbers

  • Thread starter valianth1
  • Start date
  • #1
5
0

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

 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
618

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.
 
  • #3
5
0
16(mod 17) = -1 and 18(mod 17) = 1, how do I go from here?
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
618
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?
 
Last edited:
  • #5
5
0
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
 
  • #6
I like Serena
Homework Helper
6,577
176
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.
 
  • #7
Dick
Science Advisor
Homework Helper
26,258
618
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?
 

Related Threads on Finding the mod of large numbers

Replies
1
Views
6K
  • Last Post
Replies
4
Views
2K
Replies
2
Views
796
  • Last Post
Replies
6
Views
2K
Replies
58
Views
14K
  • Last Post
Replies
17
Views
1K
Replies
2
Views
2K
Replies
1
Views
3K
Top