Number theory: Find the last three digits

[miren324]

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!

 

[Citan Uzuki]

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.

 

[miren324]

Thanks a lot. Found the proof. You may have just saved my MAT445 grade. Haha.

 

[Citan Uzuki]

You're welcome