I'm doing some exam practice questions and I am totally stuck on this one, been racking my brain for days without much progress. I would truly appreciate some help.
I tried so many different routes. But my tutor gave this following hint, but I am struggling to proceed with it, or really how it would even lead to a solution:
Start with the simplest example such that $10^n+3$ is composite with $n$ divisible by a small prime factor. I see that:
$10^4\equiv -3 (mod \space 7)$ (2 being the small prime factor obviously)
or
$10^9\equiv -3 (mod \space 23)$ (with 3 as a small prime factor)
Then he said, prove that for all $n$ > some number, that it is divisible by this small prime factor.
So using the case for $n=9$, letting $n = 3k$ for some integer $k$, I re-write this as:
$(10^{3})^k\equiv -3 (mod \space 23)$
I know $10^3\equiv -3 (mod 17)$, but I am not sure how to proceed?
I'm usually pretty good with at least going in a reasonable direction with a hint, but I am truly stuck here.
Sincere thanks in advance.
Best Answer
Although numbers of the form $10^n + 3$ (for $n=1,2,3,\ldots$) are never divisible by $2,3,5$, they are divisible by some prime $p$, possibly with the number $10^n + 3$ itself being that prime (e.g. $103$ is a prime).
Now Fermat's Little Theorem can be applied to deduce infinitely many composite numbers of the same form. That is, if $p$ divides $10^n + 3$, then $p$ is relatively prime to $10$ and:
$$ 10^{p-1} \equiv 1 \mod \; p $$
From this it follows that for every $k=1,2,3,\ldots$, we have $p$ divides $10^{n + k(p-1)} + 3$. Since $p \le 10^n + 3 \lt 10^{n + k(p-1)} + 3$, it follows that these latter numbers of the required form are composite.
Example: Since $7 | 10^4 + 3$, the numbers $10^{4+6k} + 3$ are composite.