Maths WorkshopMaths problems with full solutions
Exercise 1328Number theory › CongruencesM1Added 5 Nov 2026

A multiple of n written with only 0s and 1s

#pigeonhole#repunits#decimal digits

Statement

  1. Prove that every positive integer nn has a nonzero multiple whose decimal digits are all 00 or 11.
  2. Prove that if gcd⁡(n,10)=1\gcd(n,10)=1, then nn divides some repunit 11…111\ldots1.
Hint

Part 1: consider the repunits Rk=11…1⏟kR_k=\underbrace{11\ldots1}_{k} for k=0,1,…,nk=0,1,\dots,n (with R0=0R_0=0) modulo nn. Part 2: use Euler's theorem for the modulus 9n9n.

Show solutionHide solution

Solution

1. The n+1n+1 numbers R0,R1,…,RnR_0,R_1,\dots,R_n have only nn possible remainders modulo nn, so Ri≡Rj(modn)R_i\equiv R_j\pmod n for some 0≤i<j≤n0\le i<j\le n. Then n∣Rj−Rin\mid R_j-R_i. But Rj−RiR_j-R_i is the number made of j−i≥1j-i\ge1 ones followed by ii zeros, which is positive and uses only the digits 00 and 11.

2. Assume gcd⁡(n,10)=1\gcd(n,10)=1. Then gcd⁡(9n,10)=1\gcd(9n,10)=1 as well, so by Euler 10k≡1(mod9n)10^{k}\equiv1\pmod{9n} for k=φ(9n)k=\varphi(9n). Hence 9n∣10k−1=9Rk9n\mid10^k-1=9R_k, so n∣Rkn\mid R_k.

Check. n=7n=7: 7∣1111117\mid111111. n=3n=3: 3∣1113\mid111.

Remark. If nn has factors 22 or 55, part 2 fails, but part 1 still holds: 2∣102\mid10, 5∣105\mid10.

Lesson. Pigeonhole on a sequence of residues gives a nonzero difference divisible by nn; the structure of the sequence (Rj−RiR_j-R_i) tells you what that difference looks like.