+118613 
+118613
How many integers a from 1 to 1000 are there such that \(a^{100}-1\) is divisible by 1000?
\(\frac{a^{100}-1}{1000}=N\qquad where \qquad N\in (intergers \ge0)\)
My first thought was ... what possibilities are there for the last digit.
The last digit of a^100 must be 1 for any possible 'a' to be considered.
For convenience I will call the last digit k
Only last digit displayed
| k^1 | k^2 | k^3 | k^4 | k^5 all have a pattern now | k^100 from pattern |
| 0 | 0 | 0 | 0 | 0 | |
| 1 | 1 | 1 | 1 | 1 | |
| 2 | 4 | 8 | 6 | 2 | 6 |
| 3 | 9 | 7 | 1 | 3 | 1 |
| 4 | 6 | 4 | 6 | 4 | 6 |
| 5 | 5 | 5 | 5 | 5 | 5 |
| 6 | 6 | 6 | 6 | 6 | 6 |
| 7 | 9 | 3 | 1 | 7 | 1 |
| 8 | 4 | 2 | 6 | 8 | 6 |
| 9 | 1 | 9 | 1 | 9 | 1 |
Since k^100 must end in 1, k must end in 1,3, 7 or 9
But what about the other digits ???
\(\frac{a^{100}-1}{1000}=N\qquad where \qquad N\in (intergers \ge0)\\ \)
I am going to let a=(10x+k) I know that k must be 1,3,7, or 9 but I am not sure about restrictions on x
so using the binomial expansion I have
\((10x+k)^{100}=\displaystyle\sum_{r=0}^{100}\;(10k)^r(k)^{100-r}\)
Since I want to know if this -1 is divisable by 1000 I only care about terms that are not multiples of 1000, that is not many terms.
\((10x+k)^{100}\\=\displaystyle\sum_{r=0}^{100}\;(10k)^r(k)^{100-r}\\ =\binom{100}{0}(10x)^0(k)^{100}\;+\;\binom{100}{1}(10x)^1(k)^{99}\;+\;\binom{100}{2}(10x)^2(k)^{98}\;+\;\dots\\ =k^{100}+100(10x)(k)^{99}\;+\;4950(100x^2)(k)^{98}\;+\;\dots\\ =k^{100}+1000x*(k)^{99}\;+\;495000x^2(k)^{98}\;+\;\dots\\ =k^{100}+\;\dots\\\)
So only k, which is the last digit matters. so long as k^100 ends in 1 then \((10x+k)^{100} -1 \) will be divisable by 1000
So a can be any number at all that ends in 1,3,7,9
There are 1000 numbers between 1 and 1000
10X<1000 so
X<100
There are 100 numbers that end in 1
100 that end in 3
100 that end in 7 and
100 that end in 9
So there are 400 numbers altogether that meet the requirements. Just as our guest already determined.
+118613 +118613 
