Is every prime contained in the set $\,\{n\in\mathbb{N}:n|10^k-1\}\cup\{2,5\}\,$ for $k=1,2,3,...$?

A prime number $p$ divides $10^k-1$ if and only if $10^k \equiv 1 \bmod p$. But if $p \nmid 10$ then $10^{p-1} \equiv 1 \bmod p$ by Fermat's little theorem.

Therefore $p$ divides $10^{p-1}-1$ for all prime numbers $p \not\in \{ 2,5 \}$.


Yes: it's true that every prime $p \neq 2$ or $5$ divides some number of the form $10^k-1$.

There is a simple way to prove this fact.

Look at the remainders of $10^k-1$ when divided by $p$. Clearly there are only finitely many remainders, namely $0,1,2, \dots, p-1$. Since the numbers of the form $10^k-1$ are infinitely many, there are two of them which give the same remainder when divided by $p$.

Let's say there are $k<l$ such that $10^k-1$ and $10^l-1$ have the same remainder when divided by $p$. This is equivalent on saying that $$(10^l-1)-(10^k-1)$$ is a multiple of $p$. But $$(10^l-1)-(10^k-1) = 10^l-10^k = 10^k (10^{l-k}-1)$$ Since $p$ divides $10^k (10^{l-k}-1)$ and does not divide $10^k$, necessarily $p$ divides $(10^{l-k}-1)$. This concludes the proof.


It's a somewhat startling result that any number, prime or not, that does not have $2$ or $5$ as a factor, will have a multiple that consists only of the digit $9$.

In elementary school we learned that if $kn$ is our number that $\frac 1n$ can be written as a repeating decimal with period of $k$ digits. If we write out the $k$ digits as a single integer $K$ then if we multiply $\frac 1n = 0.\overline{K}$ by $10^k$ we got $10^k \frac 1n = K.\overline K$ and if we subtract $K$ we get $(10^k - 1)\frac 1n = K.\overline K - 0.\overline K = K$.

In elementary school we usually do that as a way to convert a repeating decimal into a fraction: $0.\overline K = \frac {K}{9999.....9}$. However it also shows that $10^k -1 = K*n$. So $n|10^k-1$ and we are done with our claim.

That's seems like a ... clunky and unsophisticated proof but it actually is valid although we have to tediously prove that converting $\frac 1n = \sum_{i=1}^{\infty} \frac {a_i}{10^i}; 0 \le a_i < 10; a_i \in \mathbb Z$ will have a unique representation and that if $2,5\not \mid n$ that one will always have a "remainder" and as there are only $n$ possible remainders there will come a time of infinite repeats. Then it really is a valid proof.

But we can probably do better.

If $2,5\not \mid n$ then $\gcd(10, n) = 1$ so by Euler's theorem

$10^{\phi (n)} \equiv 1 \pmod n$ and $10^{\phi (n)} -1 \equiv 0 \pmod n$.

And that's that.

....

I for always find it interesting when we find some simplification of clunky basic things we learned in elementary school using a simple number theory tool.