Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

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.

share|improve this answer
add comment

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!

share|improve this answer
add comment

Let me try to answer your original question.

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.