# Is there a better way of finding the order of a number modulo $n$?

Say I wish to find the order of 2 modulo 41.

The way I've been shown to compute this is to literally write out $2^k$ and keep going upwards with $0 \leq k \leq 41$, or until I observe periodicity in the sequence, and then state the order from there.

Is there a better way of deducing the order of a number with respect to some modulo?

This seems highly inefficient, especially if we are working with respect to some large modulo $N$ where it will take at most $N$ computations to determine when periodicity occurs.

• Since $41$ is prime, the order must be a factor of $40$ Nov 17, 2014 at 6:49
• I did not know this, but thanks for that. Very useful. Perhaps a bad example, what if $n$ is NOT prime? Are there any results that can further 'filter' it out? Also, say we know the order must be a factor of 40, then is there a systematic way of computing the order without having to bash out any numbers? Nov 17, 2014 at 6:51

For any $$a$$ and $$N$$ with $$\gcd(a,N)=1$$, the order of $$a$$ modulo $$N$$ must be a divisor of $$\varphi(N)$$. So if you know the prime factorization of $$N$$ (or $$N$$ is already prime) so that you can compute $$\varphi(N)$$ and also know the prime factorization of $$\varphi(N)$$, you can proceed as follows:

If we know an integer $$m>1$$ with $$a^m\equiv 1\pmod N$$ and know the prime divisors of $$m$$, for all primes $$p$$ dividing $$m$$ do the following: Compute $$a^{m/p}\bmod N$$ and if the result is $$\equiv 1\pmod N$$, replace $$m$$ with $$m/p$$ and repeat (or switch to the next prime divisor if $$m$$ is no longer divisible by $$p$$). When you have casted out all possible factors, the remaining $$m$$ is the order of $$a$$. Note that the computations $$a^m\bmod N$$ do not require $$m$$ multiplications, but rather only $$O(\log m)$$ multiplications mod $$N$$ if we use repeated squaring.

If $$N$$ is large and the fatorization of $$\varphi(N)$$ is known (and especially if you suspect the order of $$a$$ to be big), this is in fact a fast method.

Note that a couple of computations can be saved even beyon what is descibed above: In the case $$p=2$$, we may end up computing $$a^m, a^{m/2}, a^{m/4},\ldots$$ to cast out factors of $$2$$. But the later numbers were in fact intermediate results of computing $$a^m$$ by repeated squaring! Also, once we notice for some $$p$$ with $$p^k\mid m$$ that $$a^{m/p}\not\equiv 1\pmod N$$, we can save a few squarings and so speed up the task for the remaining primes if we replace $$a$$ with $$a^{p^k}\pmod N$$ and $$m$$ with $$m/p^k$$ - just remember to multiply the factor $$p^k$$ back into the final answer!

In your specific example, we know that $$N=41$$ is prime and that $$\varphi(N)=40=2^3\cdot 5$$. We check $$p=5$$ and note that $$2^{40/5}=256\equiv 10\pmod{41}$$, hence the factor $$5$$ cannot be eliminated. After that we check how many $$2$$'s we have to use: $$2^5\equiv 32\equiv -9$$, hence $$2^{10}\equiv 81\equiv -1$$, $$2^{20}\equiv (-1)^2\equiv 1$$. We conclude that $$2$$ has order $$20$$ modulo $$41$$.

The order must be one of $1,2,4,8,5,10,20,40$.

Calculate $2^2,2^4=(2^2)^2,2^8=(2^4)^2,...\\2^5=2^4*2,2^{10}=(2^5)^2,2^{20}=(2^{10})^2,2^{40}=(2^{20})^2$ which is seven calculations.

If 41 is not prime, say $41=a^2b^3c$,then

i) calculate the order of $2\pmod{a^2}$, and the order $\pmod{b^3}$ and the order $\pmod c$
ii) calculate the lowest common multiple of the separate orders.

Here we calculate the order of $$2$$ in $$(\mathbb{Z}/{41}\mathbb{Z})^\times$$.

Note: When calculating you can use the previous work to your advantage. To really cut down on the calculations, if you know the order is greater than or equal $$10$$, once you calculate $$2^{10} \pmod{41}$$ you are done,

$$\quad 2^{10} \equiv 1 \pmod{41} \quad \text{order is } 10$$
$$\quad 2^{10} \equiv 40 \pmod{41} \quad \text{order is } 20$$
$$\quad \text{NOT }[2^{10} \equiv 1, 40 \pmod{41}] \quad \text{order is } 40$$

Work Summary : $$2^1 \equiv 2 \pmod{41}$$.

The order of $$2$$ is one of $$2,4,8,5,10,20,40$$.

Work Summary : $$2^2 \equiv 4 \pmod{41}$$.

The order of $$2$$ is one of $$4,8,5,10,20,40$$.

Work Summary : $$2^4 \equiv 16 \pmod{41}$$.

The order of $$2$$ is one of $$8,5,10,20,40$$.

Work Summary : $$2^5 = \equiv 32 \pmod{41}$$.

The order of $$2$$ is one of $$8,10,20,40$$.

Work Summary : $$2^8 \equiv 10 \pmod{41}$$

The order of $$2$$ is one of $$10,20,40$$.

Work Summary : $$2^{10} \equiv 40 \pmod{41}$$

The order of $$2$$ is one of $$20,40$$.

Work Summary : $$2^{20} \equiv 1 \pmod{41}$$

The order of $$2$$ is equal to $$20$$.