2
$\begingroup$

Let $n$ be a positive odd integer which is not a multiple of $5$.

Prove that there are infinitely many integers of the form $111\ldots111$ that are multiple of $n$.

I learned about Euler's theorem and $\phi$ function, but I don't know how to solve this problem.

$\endgroup$
  • $\begingroup$ $10^{k\phi(n)}\equiv1\bmod n$, so that gives you infinitely many integers of the form $999\dots999$. So you just have to work out what to do about that unwanted factor of 9. Alternatively, see math.stackexchange.com/questions/1323907/… $\endgroup$ – Gerry Myerson Nov 6 '17 at 8:59
2
$\begingroup$

Let $n$ be your number. So, $n$ is odd and it is not a multiple of $5$. Let $N=9n$. Again, $N$ is odd and it is not a multiple of $5$. So, by the Euler-Fermat theorem, $10^{\phi(N)}\equiv1\pmod N$. And therefore, for each natural $k$, $10^{k\phi(N)}\equiv1\pmod N$. But this means that $N\mid10^{k\phi(N)}-1$, and $10^{k\phi(N)}-1$ is just a long string of $9$'s. Since $N=9n$, it follows from this that $n$ divides a long string of $1$'s of the same length. Since $k$ is arbitrary, there are infinitely many solutions.

$\endgroup$
  • $\begingroup$ "Again, $N$ is $N$" While this is definitely true, I think you meant "$N$ is odd". $\endgroup$ – Arthur Nov 6 '17 at 9:04
  • $\begingroup$ @Arthur I've edited my answer. Thanks. $\endgroup$ – José Carlos Santos Nov 6 '17 at 9:05
2
$\begingroup$

Try subtracting one of those numbers from another among $n$ consecutive such numbers and see what kind of differences you get. Note also that $n$ and 10 are relatively prime. Also note that once you find one such number, you can make infinitely many more. It's just a pigeonhole problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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