Maths WorkshopMaths problems with full solutions
Exercise 1102Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

A multiple of $n$ from $0$s and $1$s

#pigeonhole#multiples#digits

Statement

Show that for any positive integer nn coprime to 1010, there exists a multiple of nn whose decimal representation uses only the digits 00 and 11.

Hint

Consider the numbers 1,11,111,…1, 11, 111, \ldots and their residues mod nn.

Show solutionHide solution

Solution

Sequence. Consider ak=1⋯1⏟ka_k = \underbrace{1\cdots1}_{k} for k=1,…,n+1k=1,\ldots,n+1.

Pigeonhole. n+1n+1 numbers and nn residues mod nn: two have the same residue, say ai≡aj(modn)a_i\equiv a_j\pmod n with i<ji<j.

Difference. aj−ai=1⋯1⏟j−i0⋯0⏟ia_j-a_i = \underbrace{1\cdots1}_{j-i}\underbrace{0\cdots0}_{i}, which is a multiple of nn and uses only 00s and 11s.

Conclusion. A multiple with the required form exists.