Prove2Me

Every natural number has a multiple written with the digits 00 and 11 only

Proved
AlfutovaUstinov.problem_4_113

by evgeth · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

decimal-digitselementary-number-theorynumber-theorypigeonhole-principle

This is Problem 4.113 of N. B. Alfutova and A. V. Ustinov, Algebra and Number Theory (MCCME, 2002), Chapter 4, §4 “Theorems of Fermat and Euler”.

Theorem. For every natural number n≥1n\ge 1 there is a positive multiple mm of nn whose decimal representation consists only of the digits 00 and 11:

∃ m≥1:n∣mand every decimal digit of m is 0 or 1.\exists\, m\ge 1:\qquad n\mid m \quad\text{and every decimal digit of } m \text{ is } 0 \text{ or } 1 .

This is a classical pigeonhole-principle exercise; it shows, for instance, that 1/n1/n can be approximated arbitrarily well by decimal fractions built from zeros and ones.

Formalization Note The decimal digits of mm are Mathlib's Nat.digits 10 m (the list of base-1010 digits, least significant first, without leading zeros). The multiple mm is required to be positive, which excludes the trivial multiple 00.

Preamble
import Mathlib
Formal statement
namespace AlfutovaUstinov

theorem problem_4_113 (n : ℕ) (hn : 0 < n) :
    ∃ m : ℕ, 0 < m ∧ n ∣ m ∧ ∀ d ∈ Nat.digits 10 m, d = 0 ∨ d = 1 := by sorry

end AlfutovaUstinov
Source
N. B. Alfutova, A. V. Ustinov, «Алгебра и теория чисел. Сборник задач для математических школ» (Algebra and Number Theory: a problem book for mathematical schools), Moscow: MCCME, 2002, Chapter 4 «Арифметика остатков» (Arithmetic of residues), §4 «Теоремы Ферма и Эйлера» (Theorems of Fermat and Euler), Problem 4.113. Problem text and answer as catalogued on problems.ru, problem 60739: https://problems.ru/view_problem_details_new.php?id=60739

View graph