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$
1
  • $\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$ Commented Nov 6, 2017 at 8:59

2 Answers 2

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$
2
  • $\begingroup$ "Again, $N$ is $N$" While this is definitely true, I think you meant "$N$ is odd". $\endgroup$
    – Arthur
    Commented Nov 6, 2017 at 9:04
  • $\begingroup$ @Arthur I've edited my answer. Thanks. $\endgroup$ Commented Nov 6, 2017 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .