3
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – астон вілла олоф мэллбэрг Aug 29 '16 at 11:07
  • $\begingroup$ @астонвіллаолофмэллбэрг: Thank you. Struggling to get it. Will get back to you shorty I hope. $\endgroup$ – barak manos Aug 29 '16 at 11:09
  • $\begingroup$ @астонвіллаолофмэллбэрг: So how does "$10^{n-1}\equiv1\pmod{n}$" helps covering divisibility by every possible prime except $2$ and $5$? $\endgroup$ – barak manos Aug 29 '16 at 11:14
  • $\begingroup$ @астонвіллаолофмэллбэрг, make it into an answer, and I'll +1 it. $\endgroup$ – Andreas Caranti Aug 29 '16 at 11:17
  • $\begingroup$ @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. $\endgroup$ – астон вілла олоф мэллбэрг Aug 29 '16 at 11:18
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So $p\neq2,3,5 \implies p|10^{p-1}-1 \implies p|(10^{p-1}-1)/9$... Got it, thanks!!! $\endgroup$ – barak manos Aug 29 '16 at 11:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.