The Phone Number Puzzle: Can Any Integer Be Multiplied Into a Number Containing Only 0s and 1s?

A Counterintuitive Mathematical Fact

Take your phone number and treat it as a large integer. There's a surprising mathematical fact: you can always find another positive integer such that their product contains only the digits 1 and 0.

Even more striking — if your phone number ends in 1, 3, 7, or 9, you can find a multiplier whose product consists entirely of 1s, forming what's known as a repunit (e.g., 111...1).

This seems almost unbelievable at first. Any arbitrary string of digits can be "completed" into a clean combination of 0s and 1s — and behind this lies a remarkably elegant principle from number theory.

What Makes This Puzzle Challenging

This problem comes from a monthly math puzzle series, and this month's challenge is to prove why this always holds.

What makes it truly interesting is the contrast in computational approaches. If you try to find the right multiplier for your own phone number by brute-force enumeration — testing one candidate after another — the required computation will almost certainly exceed whatever computing power you have available. Once the numbers get large enough, pure trial-and-error spirals out of control.

But if you genuinely understand the underlying proof, everything changes. With that insight, you can make your "brute-force search" far smarter, dramatically narrowing the search space so that finding the answer becomes feasible in reasonable time. This is precisely the value of mathematical insight: it doesn't replace computation — it makes computation efficient.

The Number-Theoretic Intuition

While the original video leaves the full proof as an exercise for the viewer, we can point out the key ideas.

The Power of the Pigeonhole Principle

The classic tool for proving statements like this is the Pigeonhole Principle. Consider the sequence of repunits: 1, 11, 111, 1111, … When we take remainders modulo some fixed divisor, only finitely many remainders are possible. Once the count of repunits exceeds the number of possible remainders, two of them must share the same remainder. Their difference will be divisible by the target number and will consist only of 1s and 0s.

The Pigeonhole Principle is one of the most fundamental and powerful tools in combinatorics. Its statement is deceptively simple: if you place n+1 objects into n containers, at least one container must hold more than one object. Obvious as it sounds, its consequences can prove many non-trivial existence results.

Applied here: for a k-digit phone number N, consider the sequence R₁=1, R₂=11, R₃=111, … and their remainders modulo N. Remainders can only take values from 0 to N−1, giving N possible values. Among the first N+1 repunits, two must share the same remainder — call them Rᵢ and Rⱼ (i > j). Then Rᵢ − Rⱼ is divisible by N, and it takes the form 111...1000...0 (some 1s followed by some 0s) — exactly the kind of number we're looking for. If any remainder in the sequence is 0, the corresponding repunit is itself divisible by N, and the conclusion follows even more directly.

The Last Digit Determines the Form

Why does a last digit of 1, 3, 7, or 9 guarantee a product made entirely of 1s? Because these four digits are coprime to 10 — they share no factors with 2 or 5. Repunits themselves contain no factors of 2 or 5, so only numbers that are also free of these factors can divide evenly into a repunit. If the last digit is even or 5, zeros are unavoidable in the product.

"Coprime to 10" in number theory means gcd(N, 10) = 1 — that N has neither 2 nor 5 as a prime factor. This matters because of the structure of repunits: Rₙ = (10ⁿ − 1)/9, and since 10ⁿ − 1 always ends in 9, it is both odd and not divisible by 5. So Rₙ itself contains no factors of 2 or 5.

If N contains a factor of 2 or 5, it can never divide any repunit Rₙ — meaning an all-1s product simply doesn't exist, and the best achievable result is a mixed 0-and-1 number.

More precisely, when gcd(N, 10) = 1, Euler's theorem guarantees that 10^φ(N) ≡ 1 (mod N), ensuring some n exists with 10ⁿ ≡ 1 (mod N), and hence 9·Rₙ = 10ⁿ − 1 ≡ 0 (mod N). With further analysis of gcd(9, N), one can confirm that some Rₙ is indeed a multiple of N. The smallest such n is called the multiplicative order of 10 modulo N, and it directly determines the number of digits in the final answer.

From Proof to Efficient Search

Once you understand the structure of the remainder cycle, searching for the right multiplier is no longer blind trial-and-error. You only need to track when the remainder sequence first hits zero or repeats — and this period is often far smaller than the number itself. What was once an infeasible brute-force search becomes a targeted, directed lookup.

Why This Kind of Puzzle Is Worth Thinking About

The phone number puzzle distills the core appeal of mathematical thinking: what appears to be a problem about "random digits" is actually governed by divisibility, remainders, and the Pigeonhole Principle. It reminds us that many problems that seem to demand massive computation can be elegantly resolved once their structure is properly understood.

For those who enjoy getting hands-on: try it with your own phone number. First, experience the frustration of brute-force enumeration. Then feel the clarity that comes from understanding the underlying principle. That leap in efficiency — from struggle to insight — is exactly what mathematical education and computational thinking aim to convey.