String Of Ones And Zeroes


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


Euler's Totient Theorem states that, aφ(n)congruent1 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 10Pcongruent1 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 10kPcongruent1 mod n.

Hence N = 10P + 102P + ... + 10nP congruent 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 106congruent1 mod 7, it follows that N = 106 + 1012 + ... + 1042 congruent 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)greater than1, 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)congruent1 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/(22times5)=3. As HCF(10,3)=1, φ(3)=2, we know that N = 102 + 104 + 106 congruent 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?

Hint: think about 10φ(n/n).

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

Only Show Problem