Take any positive integer *d* that is not a multiple of 2 or 5. Then there is some integer *k* such that *d* × *k* has only 1’s in its decimal representation. For example, take *d* = 13. We have

13 × 8457 = 111111.

Or if we take *d* = 27,

27 × 4115226337448559670781893 = 111111111111111111111111111.

Let’s change our perspective and start with the string of 1’s. If *d* is not a multiple of 2 or 5, then there is some number made up of only 1’s that is divisible by *d*. And in fact, the number of 1’s is no more than *d*.

This theorem generalizes to any integer base *b* > 1. If *d* is relatively prime to *b*, then there is a base *b* number with *d* or fewer “digits” which is divisible by *d *[1].

The following Python code allows us to find the number *k* such that *d* × *k* has only 1’s in its base *b* representation, provided *k* is relatively prime to *b*. It returns the number of 1’s we need to string together to find a multiple of *k*. If *k* shares a factor with *b*, the code returns 0 because no string of 1’s will ever be divisible by *k*.

from math import gcd def all_ones(n, b = 10): return sum(b**i for i in range(n)) def find_multiple(k, b = 10): if gcd(k, b) > 1: return 0 for n in range(1, k+1): if all_ones(n, b) % k == 0: return n

The two Python functions above default to base 10 if a base isn’t provided.

We could find a multiple of 5 whose hexadecimal representation is all 1’s by calling

print(find_multiple(5, 16))

and this tells us that 11111_{sixteen} is a multiple of 5, and in fact

5 × 369d_{sixteen} = 11111_{sixteen}.

[1] Elmer K. Hayashi. Factoring Integers Whose Digits Are all Ones. Mathematics Magazine, Vol. 49, No. 1 (Jan., 1976), pp. 19-22