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

Question

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

Let $p\notin\{2,5\}$ be a prime number. Then $\frac{1}{p}$ has a decimal period of length at most $p-1$. Denote $\frac{1}{p}$ by $$\frac{1}{p}=0.\overline{d_1d_2...d_r}$$ where $1\leq r \lt p$ and $d_i\in\{0,1,2,...,9\}$.

Let $d=0.d_1d_2...d_r\cdot10^r\;$ (e.g., if $p=7$, then $\frac{1}{7}=0.\overline{142857}$, $r=6$, and $d=142857$).

Let's consider $\frac{1}{10^m-1}$ for some $m\in\mathbb{N}$: $$ \frac{1}{10^m-1}=\frac{1}{\underbrace{99...9}_{\text{$m$ times}}}=0.\overline{\underbrace{00...0}_{m-1 \\ \text{times}}1}=\sum_{i=1}^\infty \frac{1}{10^{i\cdot m}} $$

So \begin{align} \frac{1}{p}&=0.\overline{d_1d_2...d_r}=d\cdot \left(\frac{1}{10^r}\right)+d\cdot \left(\frac{1}{10^{2r}}\right)+d\cdot \left(\frac{1}{10^{3r}}\right)+\cdots \\ &=d\cdot\left(\frac{1}{10^r}+\frac{1}{10^{2r}}+\frac{1}{10^{3r}}+\cdots\right) \\ &=d\cdot\sum_{i=1}^\infty \frac{1}{10^{i\cdot r}} \\ &=\frac{d}{10^r-1} \end{align}

Rearranging terms, we have $\,10^r-1=p\cdot d \, \Longrightarrow \, p|10^r-1$.

Does this prove that the set of primes is contained in the set $\{n\in\mathbb{N}:n|10^k-1\}\cup\{2,5\}$?

Clearly, $2$ and $5$ are missing from $\{n\in\mathbb{N}:n|10^k-1\}$. Are there any other primes not contained in this set?

Answer 1

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.

Answer 2

You are correct that $2$ and $5$ are the only primes that are not factors of $10^k-1$ for some natural number $k$. Your proof looks correct, but it can be shown more simply. Assuming as you have that for $p$ not equal to $2$ or $5$, $\frac{1}{p}=0.\overline{d_1d_2...d_r}$, notice (or show — it’s not too hard) that $$\displaystyle{1\over p}=0.\overline{d_1d_2...d_r}={d_1d_2...d_r\over {\underbrace{9\cdots9}_{r\ {\text 9s}}}},\ \mbox{ so that}$$ $$p\cdot d_1d_2...d_r={\underbrace{9\cdots9}_{r\ {\text 9s}}}.$$

Answer 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 \}$.

Answer 4

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.