mathschallenge.net

Problem

Prove that there always exists a number made up of ones and zeroes that is divisible by the positive integer, n.

Solution

Euler's Totient Theorem states that, a^φ(n)1 mod n, if HCF(a,n)=1.

We shall begin by considering the case where n is prime, and for brevity, we shall write φ(n)=P.

Clearly 10^P1 mod n will be true, as n is prime and we know that HCF(10,n)=1. Raising both sides of the congruence to the power, k, we get 10^kP1 mod n.

Hence N = 10^P + 10^2P + ... + 10^nP 0 mod n.

In other words, there exists a number, N, made up of ones and zeroes that is divisible by n, if n is prime.

For example, when n=7, φ(7)=6, and as 10⁶1 mod 7, it follows that N = 10⁶ + 10¹² + ... + 10⁴² 0 mod 7.

If n is composite, HCF(10,n) may not be 1, and we cannot make use of Euler's Totient Theorem. However, if HCF(10,n)1, this factor must be exclusively made up of 2's and 5's. Therefore, there exists some number, h, of the form 2^a5^b such that HCF(10,n/h)=1.

Clearly 10^φ(n/h)1 mod n/h, and so there must exist a number, N, made up of ones and zeroes that is divisible by n/h.

In which case, we can multiply N by 10 as many times as necessary so that 10^mN is still made up of ones and zeroes, but will be divisible by n. In fact, m=max(a,b); can you see why?

For example, when n=60, 60/(2²5)=3. As HCF(10,3)=1, φ(3)=2, we know that N = 10² + 10⁴ + 10⁶ 0 mod 3. Hence 100N will be made up of ones and zeroes and, being divisible by 300, must be divisible by 60.

Note that this method only proves the existence of such a number, but it does not provide the smallest such case. In the example given it turns out that N = 10² + 10⁴ + 10⁶ = 1010100 is already divisible by 60 before multiplying by 100.

Can you find a more optimal approach?