Finding the mod of large numbers

In summary, to evaluate (16^1000 - 18^2000)(mod 17), we can use the fact that 16 and 18 are congruent to -1 and 1 mod 17, respectively. This allows us to rewrite the equation as (-1)^1000-1^2000(mod 17). Since (-1)^1000 = 1, the solution simplifies to 1-1(mod 17), which is equal to 0 (mod 17). Therefore, the solution to the equation is 0.
  • #1
valianth1
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 realize it has something to do with the pattern from the last digit obtained from the 2 large numbers


The Attempt at a Solution

 
Physics news on Phys.org
  • #2
valianth1 said:

Homework Statement



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


Homework Equations



I'm not sure how to go about doing this, but I realize 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
16(mod 17) = -1 and 18(mod 17) = 1, how do I go from here?
 
  • #4
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?
 
Last edited:
  • #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
 
  • #6
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
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?
 

1. What does "finding the mod of large numbers" mean?

The mod of a number is the remainder after dividing that number by another number. Finding the mod of large numbers involves calculating the remainder after dividing a large number by another number.

2. Why is finding the mod of large numbers important?

Finding the mod of large numbers is important in many fields, including mathematics, computer science, and cryptography. It is used in algorithms and equations to solve complex problems and can also be used to ensure data integrity and security.

3. How do you find the mod of large numbers?

To find the mod of large numbers, you can use the modulo operator (%) in most programming languages. In mathematics, you can use the division algorithm or long division to find the remainder. There are also various algorithms and methods specifically designed for finding the mod of large numbers.

4. What are some applications of finding the mod of large numbers?

Applications of finding the mod of large numbers include cryptography, where it is used to ensure the security of data and communications. It is also used in computing, particularly in programming languages and algorithms that involve division. In mathematics, it is used in number theory and can help solve problems related to prime numbers and modular arithmetic.

5. Is there a limit to the size of numbers that can be used when finding the mod?

Technically, there is no limit to the size of numbers that can be used when finding the mod. However, as the numbers get larger, the calculations required to find the mod can become more complex and time-consuming. In practical applications, there may be limitations based on computational power and the resources available.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
19
Views
1K
  • Precalculus Mathematics Homework Help
Replies
32
Views
800
  • Precalculus Mathematics Homework Help
Replies
21
Views
747
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
12
Views
953
  • Precalculus Mathematics Homework Help
Replies
28
Views
3K
  • Precalculus Mathematics Homework Help
Replies
13
Views
2K
  • Precalculus Mathematics Homework Help
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
Back
Top