## String Of Ones And Zeroes

#### 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 10P1 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 10kP1 mod n.

Hence N = 10P + 102P + ... + 10nP 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 1061 mod 7, it follows that N = 106 + 1012 + ... + 1042 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 2a5b 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 10mN 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/(225)=3. As HCF(10,3)=1, φ(3)=2, we know that N = 102 + 104 + 106 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 = 102 + 104 + 106 = 1010100 is already divisible by 60 before multiplying by 100.

Can you find a more optimal approach?

Problem ID: 187 (01 Nov 2004)     Difficulty: 4 Star

Only Show Problem