Earlier in the week, while tutoring in the math lab, a student came to me asking for assistance on proving the following statement:
$$1994\mid 10^{900}-2^{1000}$$
The numbers were much too large to attempt to brute force, $1994 = 2\cdot 997$ and $997$ is prime, so Fermat's little theorem is of little help here.
Factoring $10^{900}-2^{1000} = 2^{900}(5^{450}+2^{50})(5^{225}+2^{25})(5^{225}-2^{25})$ reduces the problem to seeing if $997$ divides any of the above terms, but that didn't seem to help much either as again, the numbers involved are so large.
I was able to make a claim which if true would lead to a solution, but had no way of expecting to be true ahead of time, namely that $1994\mid 10^{9k}-2^{10k}$ for each $k$. As it so happens, this claim turned out to be true which yields the desired result by setting $k=100$. Giving him the claim as a clue, he was able to proceed.
As it required proving a much stronger statement first and taking a stab in the dark, I wondered if this was indeed the intended solution or if there is something that I missed that yields the result a bit more easily.
Is there a better/alternative way to prove this?
Short version of my proof:
Let $k=1$. Then $10^{9}-2^{10} = 999998976=1994\cdot 501504$ so the base case holds.
Assume claim holds for some $k\geq 1$. Then for $k+1$ we have:
$10^{9(k+1)}-2^{10(k+1)} = 10^910^{9k}-2^{10}2^{10k} = (10^9+2^{10}-2^{10})10^{9k}-2^{10}2^{10k}$
$=2^{10}(10^{9k}-2^{10k})+(10^9-2^{10})10^{9k}$ which is the sum of numbers divisible by $1994$, proving the claim.
We have $$10^{900}=1000^{300}\equiv 3^{300}\pmod{997}.$$ Also $$2^{1000}=(2^{10})^{100}\equiv (-27)^{100}\equiv (-3)^{300}\equiv 3^{300} \pmod{997}.$$
Thus $10^{900}-2^{1000}\equiv 0\pmod{997}$. And of course $10^{900}-2^{1000}\equiv 0\pmod{2}$.