Skip to content

Every integer divides some number made of 1s and 0s

Question

Prove that for each positive integer nn there exists a positive multiple of nn whose decimal digits are all 00 or 11.

Short answer

Use the pigeonhole principle on repunits. Look at 1,11,111,…1, 11, 111, \dots up to the number with n+1n+1 ones. There are n+1n+1 of them but only nn residues mod nn, so two share a remainder. Their difference is divisible by nn and has the form 11⋯1 00⋯011\cdots1\,00\cdots0, which uses only the digits 11 and 00.

Adapted from Wilmott, Frequently Asked Questions in Quantitative Finance, ch. 10 brainteaser 'Ones and zeros', p.354; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution