find least multiple formed only of 1's of given number

Question

The problem states that given a number find the least multiple formed only of 1's. If no such number exists then 0 will be the answer.

For example for:

3 the answer is 111
4 the answer is 0, no such number exists
7 the answer is 111111

I think it has something to do with the prime numbers but I don't know what exactly.

Is there a known algorithm/problem to solve this? In particular, how to find if a solution exists?

Thanks in advance.

Answer 1

Here is a sample computation. Suppose the number you start with is 29. Thus, you want to find the shortest string of 1's divisible by 29. Equivalently, you want the smallest positive integer n such that $$10^n-1 \equiv 0 \;\;\;mod (29)$$ (to see this note that the left hand is a string of n 9's but, as 9 and 29 are relatively prime, we can divide by 9 without changing the congruence). This is equivalent to asking: "What is the order of 10 mod (29)?". General Theory tells us that this order has to be a divisor of $\phi$(29) = 28. Thus the only n we need to check are the divisors of 28, so n $\in$ {2, 4, 7, 14, 28}. Working mod(29) it isn't difficult to confirm that the answer is n = 28. The calculation is slightly more difficult if your starting number, A, is divisible by 3 (for then we can not effortlessly divide the congruence by 9). In that case, just work with the congruence mod(9A). If A is divisible by either 2 or 5 then there is no n which works (as the associated congruence is clearly not possible).