Using Euler’s Theorem, prove that if n is a number not divisible by 2 or 5, then n divides a number consisting of all 9’s.

Question

Using Euler’s Theorem, prove that if n is a number not divisible by 2 or 5, then n divides a number consisting of all 9’s.

If n is not a number divisible by 2 or 5, then the number $n$ is odd and does not end in a 0 or 5. These are some divisibility rules that come to mind, but what can I do with these?

Answer 1

Theorem: (Euler) Suppose that a is relatively prime to n. Then $a^{φ(n)}≡1 (mod n)$.

Suppose now that n is divisible neither by 2 nor by 5, and let a=10. Then a and n are relatively prime, and therefore $$10^{φ(n)}≡1(modn)$$ For any k≥1, the number $10^k−1$ has decimal representation that consists only of 9's. So we have shown that if n is divisible neither by 2 nor by 5, then the number consisting of φ(n) 9's is divisible by n.

Answer 2

The thing about a number consisting of all $9$'s is that it's equal to $10^k-1$, where $k$ is some positive integer. If a prime $p$ divides such a number, that means that $10^k\equiv 1\pmod{p}$. Does Euler's theorem give you any reason to think that such a $k$ exists, when $p$ is a prime other than $2$ or $5$?