Formula for smallest multiple of given number, whose every digit is 1

Question

Introduction

I've been solving a problem, which says which number is the smallest multiple of $x$ which only has digits with value 1.
For example: $minOnes(3) = 3 -> 111$;
$minOnes(7) = 6 -> 111111$
$minOnes(11) = 2 -> 11$;
$minOnes(2601) = 2448$.

I have been playing with numbers, and have reached to a formula. If $x$ is our number to solve.

Formula

$minOnes(x) = minOnes( mcm(minOnes(divisors[x])) * ( divisor[x]$ ^ ($times$_$appeared$-$1$) for each $divisor$ in $divisors$) )

divisors are all the divisors of $x$. For example, 21 has 3 and 7 as divisors.
times_appeared is the number of times the divisor divides $x$. For example, 3 divides 3 times 27. mcm(..) is the minimum common multiple of the minOnes() of its divisors.

Example

$63 = 3 \times 3 \times 7$
$minOnes(3) = 3$; $ minOnes(7) = 6$;
$minOnes(63) = mcm(6, 3)\times 3^1 \times 7^0 = 6\times 3 = 18$

Counter-example

Well... I have tried this formula to lot of numbers, and everything went correct. Except one: 3249 = $(3^2)(19^2)$. $minOnes(3249) = 342$, but with my formula, $minOnes(3249) = 1026 = (342)(3)$. There are maybe more numbers that don't follow this rule, but this surprises me because the formula works with almost each number.

I wanted to let it be known, if someone knows the answer or hasinterest in this :)

Note: numbers with divisors 2 and 5 are excluyed (they get a digit with 0).

Edit

I have tried with more numbers, and indeed there are more numbers which do not follow the rule. They are a few, and obey some pattern:

$171 = 3^2 \times 19$;
$513 = 3^3 \times 19$; $981 = 3^2 \times 109$;
$1197 = 3^2 \times 7 \times 19$;
$1421 = 7^2 \times 29$;
$1467 = 3^2 \times 163$;
$1539= 3^4 \times 19$;
$1629 = 3^2 \times 181$;
$1791 = 3^2 \times 199$;
$... 1881$ $2107$ $2223$ $2763$ $2783$ $2907$ $2943$ $3249$ $3411$ $3479$ $3573$

So strange...

Answer 1

As dez pointed such a number exists if and only if $\gcd(n,10)=1$.$\newcommand{\ord}{\operatorname{ord}}$

Case 1 $3 \nmid x$. Then $$x |111...1 \Leftrightarrow x|999...9 \Leftrightarrow 10^n \equiv 1 \pmod(x) \Leftrightarrow \ord_x(10)|n$$

Therefore, the smallest $n$ is
$$n=\ord_x(10)$$ that is the order of $10$ modulo $n$.

Case 2 $3 \mid x$. Then $$x |111...1 \Leftrightarrow 9x|999...9 \Leftrightarrow 10^n \equiv 1 \pmod(9x) \Leftrightarrow ord_{9x}(10)|n$$

Therefore, the smallest $n$ is
$$n=\ord_{9x}(10)$$

Note that one can use Case 2 to cover case 1 too, but the order of 10 is easier to calculate $\pmod{x}$ instead of $\pmod{9x}$.

How to actually calculate

By Euler theorem, $ \ord_{9x}(10)|\phi(9x)$, thus you need to find the smallest divisor of $\phi(9x)$ such that $10^d \equiv 1 \pmod{9x}$. (and similarly for case 1).

If you are familiar with the Chinese reminder theorem, you can use the prime factorization of $9x$ as dezdichado suggested.

P.S. interesting fact: It is easy to prove that for $gcd(k,10)=1$ we have: $\ord_{k}(10)$ is equal to the lenght of the period in $\frac{1}{k}$.

Added To calculate, here is how one should proceed:

If $k=p_1^{\alpha_1}\cdot...\cdot p_n^{\alpha_n}$ then by the Chinese Remainder Theorem $$ord_k(10)= LCM[ ord{p_1^{\alpha_1}}(10),ord{p_2^{\alpha_2}}(10),.., ord{p_n^{\alpha_n}}(10)$$

This means that you only need to figure $ord{p_j^{\alpha_j}}(10)$.

The question boils down to how to calculate $\ord_{p^\alpha}(10)$. This can be done recursively:

$$ord_p(10)|p-1$$ by Fermat Little Theorem. Also

$$\ord_{p^\alpha}(10)| \ord_{p^(\alpha+1)}(10) | p^\alpha(p-1)$$ which reduces somewhat the calculation of the order modulo $p-1$.

Therefore, if $d= \ord_{p^\alpha}(10)$ you need to find the smallest $k$ which divides $\frac{p^\alpha(p-1)}{\ord_{p^\alpha}(10)}$ such that $$p^{\alpha+1}|10^{kd}-1$$

Note that if $p^{\alpha+1}|10^{d}-1$, you are done, otherwise the problem is equivalent to finding the smallest such $k$ so that $$p| 1+10^d+10^{2d}+..+10^{(k-1)d}$$

Answer 2

Your question is equivalent to asking what is the smallest $n$ such that $10^n-1$ is divisible by given number $x$. Such a number exists if and only if $\gcd(10,x) = 1$. So what you need to do is solve the problem for $2^n-1$ and $5^n-1$, and take their least common multiple. You only need to consider the prime power divisors of $n$, not all the divisors of $n$. In other words, if $n = p_1^{a_1}...p_k^{a_k}$, then only consider each $p_i^{a_i}$ in your formula.