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!