# Several Strings of 1s

*This puzzle was in February’s MathsJam Shout, contributed by the Antwerp MathsJam. Visit mathsjam.com to find your nearest event!*

Consider the set ${1, 11, 111, …}$ with 2017 elements. Show that at least one of the elements is a multiple of 2017.

The *Shout* describes this one as tough; you might want to have a go at it yourself before reading some possible answers.

### Brute force

Naturally, my first thought was: why don’t I divide a string of 1s by 2017 and see what I get?

There’s a very good reason why not. It turns out (according to Wolfram|Alpha) to be a 2012-digit long number, and some of us have Set to play.

### A questionable approach

This is the best thing I came up with on the night, and I’m not 100% convinced it’s watertight. I’d be interested to hear an expert opinion. The outline goes:

- Write the set as $\left\{ \frac{10^{k}-1}{9} \middle| k \in \left\{0, 1, 2, 3, … 2016 \right\} \right\}$
- This has an element divisible by 2017 if $10^k = 1 \pmod {2017 \times 9}$ for some integer $k$ such that $0 \le k \le 2016$
- 10 is coprime to $2017 \times 9$. Therefore it a) has a multiplicative inverse modulo $2017\times 9$ and b) has an order of at most 2016.
- Therefore, such a $k$ exists and one of the elements in the set is a multiple of 2017.

Reading that through again, I’m moderately happy with it. I can do better, though.

### A better approach

There was this bloke, Fermat. He’s known for a few things: more or less inventing probability, for which we’ll forgive him, for Fermat’s Last Theorem, a thorn in the side of number theory and page layout experts for 350-odd years, and - most to the point, Fermat’s *Little* Theorem, which a decent undergraduate number theorist can prove in a moderate-sized margin.

It says: if $p$ is prime and $a$ is an integer, then $a^p - a$ is a multiple of $p$.

In particular, 2017 is prime, and 10 is an integer, so $10^{2017}-10$ is a multiple of 2017. Ten is not a factor of 2017 (because 2017 is prime), so $10^{2016}-1$ is also a multiple of 2017, and consists of 2016 nines strung together. Nine is not a factor of 2017 (because 2017 is *still* prime), and $\frac{10^{2016}-1}{9}$ is the last element of the given set.

### Dominika’s approach

Of course, Dominika saw another way, using the pigeonhole principle. There are 2017 elements in the set, and 2017 possible remainders modulo 2017, which means either:

- every element in the set has a different remainder modulo 2017, in which case one of them must have a remainder of 0; or
- two distinct elements (say $m$ and $n$, with $m>n$) in the set have the same remainder, in which case $m-n$ is a multiple of 2017 and consists of a string of 1s followed by a string of n 0s. Since $10^n$ is coprime with 2017, $\frac{m-n}{10^n}$ is also a multiple of 2017, and consists of a string of $m-n$ 1s - meaning it’s a multiple of 2017 and is in the given set.

A lovely puzzle, and well worth a trip through to Poole!