# Lowest multiple with given condition

I've got this interesting problem:

Find the lowest multiple of $130013$ that consists of only digit $9$ in base-$10$ numeral system.

It came down to finding the lowest $n$ such that:

$\begin{cases} 10^n \equiv 1 \pmod{13} \\ 10^n \equiv 1 \pmod{73} \\ 10^n \equiv 1 \pmod{137} \end{cases}$

And with help of my calculator I found out that $n=\text{lcm}(6,8,8)=24$. Because $10^{\phi(p)}\equiv_p 1$ for prime $p$ so I have to check all divisors of consecutively: $12,\ 72, \ 136$, as candidates. But unfortunately there are many divisors of those numbers in total, and it leads to many calculations.

So my question is: is it any simpler way to find order of given element from multiplicative group $\mathbb{Z}_p^*$? I suppose the answer is unfortunately negative. So maybe at least in this particular case it is easier, maybe some useful trick I can use here?

-

A number that can be written as a 999...999 has the form $10^n - 1$.

Observe that $7 * 11 * 130013 = 7 * 11 * 13 * 10001 = 1001 * 10001 = (10^3+1) \times (10^4 + 1)$.

Recall the factorization of $a^n - b^n$, this tells us that $10^3 + 1$ and $10^4 + 1$ are factors of $10^n +1$ if $n$ is twice a multiple of 3 and 4, or that $n$ is a multiple of 24. (As Maesumi points out, $10^{24} - 1$ works.)

Now, consider the smallest value of $n$ that works. If it is smaller than 24, then $n$ must be a factor of 24. Since we know that $10^4 + 1$ is also a factor of $10^n -1$, this tells us that $n$ must be a multiple of 8. Hence, $n=8$ is the only other possibility. However, $10^ 8 -1 \not \equiv 0 \pmod{13}$. Hence we are done.

-

Not the answer you want but I did basic multiplication adjusting digits as I needed to make nines, and I got

$130013 \times 7,691,538,538,453,846,923=10^{24}-1$.

Hurray, I can postpone retirement one more year!

-

Problem: Efficiently compute the order of an element $a$ of the multiplicative group $\mathbb Z^*_n$.

In your computation, you implicitly used the fact, that the order is a divisor of $\varphi(n)$. So what always works, is checking $a^d=1$ for all $d\mid \varphi(n)$ (you can exclude $d=\varphi(n)$, as this is always true). A natural number $m\in \mathbb N$ has are at most $\log_2m$ non-trivial divisors, thus you need to at most $\log_2\varphi(n)$ checks with this method. (There are $7$ non-trivial divisors of $\varphi(137)=136$ in your case). I assume, you used this method.

If you know the factorization of $\varphi(n)$, it gets easier, you can reduce the number of checks to $\log_2\log_2\varphi(n)$.

Note: Computing the factorization is much more expensive. But as you were trying to manual calculate this, I assume, that it is easy for you to retrieve the factorization (In this case: $136=2^3\cdot 17$).

Algorithm: Write $\varphi(n)=p_1^{e_1}\cdot\dots\cdot p_k^{e_k}$, then the order of $a$ is of the form $$p_1^{d_1}\cdot\dots\cdot p_k^{d_k} \text{ for } 0\leq d_i\leq e_i$$ Now for each $i$ do the following. For $c$ between $0$ and $e_i$, we have $$a^{p_1^{e_1}\cdot\dots\cdot p_i^c\cdot\dots\cdot p_k^{e_k}}=1 \Leftrightarrow p_1^{d_1}\cdot\dots\cdot p_k^{d_k} \mid p_1^{e_1}\cdot\dots\cdot p_i^c\cdot\dots\cdot p_k^{e_k} \Leftrightarrow d_i\leq c$$ Start with $c=\lfloor\frac{e_i}{2}\rfloor$, if the above check holds, then conclude $d_i\leq c$, otherwise $d_i>c$. Continue with binary search by halving the respective interval. You will need at most $\log_2(e_i)$ checks.

Example: $136=2^3\cdot 17$. The order of $10$ is $2^{d_1}\cdot 17^{d_2}$, where $0\leq d_1\leq 3,0\leq d_2\leq 1$.

• Calculate $d_1$:
• Check $2^1\cdot 17$: We have $10^{2^1\cdot 17}=100\not\equiv 1\pmod{137}$. So $d_1>1$.
• Check $2^2\cdot 17$: We have $10^{2^2\cdot 17}=-1\not\equiv 1\pmod{137}$. So $d_1>2$, thus $d_1=3$.
• Calculate $d_2$:
• Check $2^3\cdot 17^0$: We have $10^{2^3}=\equiv 1\pmod{137}$. So $d_1\leq 0$ and $d_1=0$.

Together: $2^{d_1}\cdot 17^{d_2}=2^3\cdot 17^0=8$.

-