Exercise 1328Number theory › CongruencesM1Added 5 Nov 2026
A multiple of n written with only 0s and 1s
#pigeonhole#repunits#decimal digits
Statement
- Prove that every positive integer has a nonzero multiple whose decimal digits are all or .
- Prove that if , then divides some repunit .
Hint
Part 1: consider the repunits for (with ) modulo . Part 2: use Euler's theorem for the modulus .
Show solutionHide solution
Solution
1. The numbers have only possible remainders modulo , so for some . Then . But is the number made of ones followed by zeros, which is positive and uses only the digits and .
2. Assume . Then as well, so by Euler for . Hence , so .
Check. : . : .
Remark. If has factors or , part 2 fails, but part 1 still holds: , .
Lesson. Pigeonhole on a sequence of residues gives a nonzero difference divisible by ; the structure of the sequence () tells you what that difference looks like.