- #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!
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!