# Prove that every prime except for $2$ and $5$ is a factor of some number of the form $111\dots1$ [duplicate]

How do we prove that for every prime $p\neq2,5$ there exists a positive integer $n$ such that $(10^n-1)/9$ is divisible by $p$?

BTW, I suspect that it holds not only in base $10$, but also in every other base $b$, for every prime which is not a factor of $b$.

My work so far - not much, except for manually testing the first few numbers of the form $111\dots1$:

• $11=11$
• $111=3\cdot37$
• $1111=11\cdot101$
• $11111=41\cdot271$
• $111111=3\cdot7\cdot11\cdot13\cdot37$
• $1111111=239\cdot4649$
• $11111111=11\cdot73\cdot101\cdot137$

Thanks

• Use pigeonhole principle, or use the fact that $10^{n-1} \equiv 1 \mod n$ whenever $n$ and $10$ are co-prime. Similarly it will follow for other bases. – астон вілла олоф мэллбэрг Aug 29 '16 at 11:07
• @астонвіллаолофмэллбэрг: Thank you. Struggling to get it. Will get back to you shorty I hope. – barak manos Aug 29 '16 at 11:09
• @астонвіллаолофмэллбэрг: So how does "$10^{n-1}\equiv1\pmod{n}$" helps covering divisibility by every possible prime except $2$ and $5$? – barak manos Aug 29 '16 at 11:14
• @астонвіллаолофмэллбэрг, make it into an answer, and I'll +1 it. – Andreas Caranti Aug 29 '16 at 11:17
• @AndreasCaranti Thank you,but unfortunately I'll keep this as a hint, it's too short as an answer. In return, please comment next time you are answering, and I can compliment you. – астон вілла олоф мэллбэрг Aug 29 '16 at 11:18

Fermat's theorem for prime $p\ne2,5$ implies $10^{p-1}-1\equiv0\pmod p$ as gcd$(10,p)=1$ in this case. Now factor out $9$ from $10^{p-1}-1$, you have what you want for $p\ne3$. For 3 you have already shown it.
• So $p\neq2,3,5 \implies p|10^{p-1}-1 \implies p|(10^{p-1}-1)/9$... Got it, thanks!!! – barak manos Aug 29 '16 at 11:17