For the benefit of anyone who prefers text:

Let $n$ be a positive integer not divisible by 2 or 5. Prove that there exists a multiple of $n$, all of whose digits are 1s.

I’m going to try solving this “live” – although it’s a bit of a cheat, because I’ve got a good idea of how it might go. In any case, spoilers below the line.

My first thought is: I know that the reciprocal of any number whose factors aren’t all powers of 2 and 5 can be written as a recurring decimal. I believe it’s the case that the reciprocal of any number with no powers of 2 and 5 can be written as a purely recurring decimal – that is, the recurring part starts immediately after the decimal point.

Change of plan

… I got up to make a cup of tea, and another idea struck me that I think might be better. I’m going to explore it, and come back to the other one afterwards.

Consider the set of numbers $\left\{ 1, 11, 111, \dots, 1\dots1 \right\}$, where the last number consists of $n$ 1s, and consider all of their remainders when you divide them by $n$.

For example, if $n=7$, our numbers are $\left\{1, 11, 111, 1111, 11111, 111111, 1111111 \right\}$, and when you divide them by seven you get remainders of $\left\{ 1, 4, 6, 5, 2, 0, 1\right\}$.

With seven remainders, that’s not difficult. We can see the 0, it’s right there! With a huge number, though, it’s a bit more tricky. But we can reason:

  • The list of remainders has $n$ entries in it
  • All of them are between 0 and $n-1$, because that’s how remainders work
  • Either all of the remainders are different, or at least two of them are the same.
  • If they’re all different, then one of them must be 0 – which means there’s a number consisting only of 1s that you can divide by $n$.
  • Failing that, suppose two of the remainders are the same – suppose $x_a \pmod n \equiv x_b \pmod n$, where $x_a$ consists of $a$ 1s and $x_b$ consists of $b$ 1s. Then $| x_a - x_b|$:
    • is a multiple of $n$
    • consists of $|a-b|$ 1s followed by $m$ 0s, where $m = \min(a,b)$
  • This can be factorised as $x_{|a-b|} \times 2^m \times 5^m$.
  • But $n$ shares no factors with $2^m$ or $5^m$, so it is a factor of $x_{|a-b|}$ – which is a multiple of $n$ consisting only of 1s!

That can probably be tidied up a bit. I’m doing it live, remember?

Back to the other way

Feels a bit pedestrian now, tbh.

In any case, if $\frac 1n$ is a purely recurring decimal with a period of $k$ ((The period of a recurring decimal is how many digits long the recurring section is – $0.\dot 14285\dot 7$ has a period of 6.)), it can be written as $d + d \times 10^{-k} + d \times 10^{-2k} + \dots$, where $d$ is the number formed by the recurring digits.

That’s a geometric sequence: it works out to be $\frac{1}{n} = \frac{d}{10^k - 1}$.

Or, rearranged, $nd = {10^k -1}$. That right-hand side is made up of $k$ 9s – so I’ve shown that there’s a multiple of $n$ that can be written only using nines. If $n$ isn’t a multiple of 9, happy days: $d$ must be, and we can divide both sides by 9 to get a multiple of $n$ that’s written using only 1s.

It it’s not, we need to be a bit cleverer: if we concatenate nine copies of $d$ together and call the result $d_9$, we get an interesting number: it’s a multiple of 9, and $nd_9 = 10^{9k}-1$. ((Can you see why?))

Then, if you divide $d_9$ and the right-hand side by 9, you get $d \frac{d_9}{9} = 1111\dots1$ as required.

I think the middle method is neater than the outer one – but I’d be interested to hear if you have a different approach!

* Edited 2022-10-10 to fix formatting. Thanks, Andrew!