Number theory: Find the last three digits

In summary, the conversation discusses how to prove that the last three digits of n^100 can only be 000, 001, 376, or 625. The method involves working with modular arithmetic and using Euler's theorem to handle cases where n is divisible by 5. It also discusses how this proof may have saved the speaker's grade in MAT445.
  • #1
miren324
14
0
Prove that the last three digits of n^100 can be only: 000, 001, 376, or 625.

I can easily show that the last digit is either 0, 1, 6 or 5 because n^100=((n^25)^2)^2, so if our last three digits are 100a+10b+c, with a, b, c belonging to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, any digit for c squared, then squared again (i.e. any last digit for n^25) would be either 0, 1, 6, 5. Where I run into trouble is trying to go beyond this.

I tried a couple of things but got nowhere. First, I said if the last three digits of n^25 are of the form 100a+10b+c, then I tried raising this to the power of 2 or 4, and dropping anything that's two large to consider (for instance, when squaring we get 10000(a^2) as a term, but this doesn't concern us since we are only interested in the 100x+10y+z terms). This yields, for squared, 100(2ac+b^2)+10(2bc)+c^2, and for raising to the 4th power, 100(2(2ac+b^2)c^2+(2bc)^2)+10(2(2bc)c^2)+c^4. These numbers are still too large to deal with (too many possible combinations of bc or c^2, etc.). There are 37 possibilities for a 2ac or 2bc term and 6 possibilities for a c^2 or b^2 term, so for 100(2ac+b^2) I would have to test 81*6 possibilities just to find the third digit.

I also tried assuming the last digit is 0 or 1 or 6 or 5, then deducing a second and third digit, but this too leads to too many possible combinations of a's, b's and c's.

I'm stuck. I need help. Thanks!
 
Physics news on Phys.org
  • #2
Since you're only trying to find the last 3 digits, you can work mod 1000, which by the chinese remainder theorem is the same as working mod 8 and mod 125. For the mod 125 calculation, divide into two cases -- where n is divisible by 5 and where it isn't. Employ Euler's theorem on the latter case. The mod 8 calculation may be handled the same way.
 
  • #3
Thanks a lot. Found the proof. You may have just saved my MAT445 grade. Haha.
 
  • #4
You're welcome :smile:
 

What is number theory?

Number theory is a branch of mathematics that deals with the properties and relationships of numbers, particularly integers.

What is the significance of finding the last three digits in number theory?

The last three digits of a number can give important information about its properties, such as divisibility, congruence, and patterns.

What strategies are commonly used to find the last three digits?

Some common strategies include using modular arithmetic, applying the Chinese Remainder Theorem, and using patterns and divisibility rules.

What is the difference between the last three digits and the last digit?

The last digit of a number refers to the digit in the ones place, while the last three digits refer to the three digits in the hundreds, tens, and ones place.

Can the last three digits of a number be predicted?

In some cases, the last three digits of a number can be predicted using certain patterns and rules. However, in most cases, the last three digits cannot be predicted without performing calculations.

Similar threads

Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
19
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
2
Views
266
  • Calculus and Beyond Homework Help
Replies
32
Views
2K
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
261
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
Back
Top