Order of cyclic subgroups in $\mathbb{Z}/n\mathbb{Z}$

Question

I'm interested in efficiently computing minimal $x$, s.t. $a^x \equiv 1 \pmod{n}$, where $\gcd(a, n) = 1$. Let's denote order of cyclic multiplicative subgroup $\langle a\rangle$ in $\mathbb{Z}/n\mathbb{Z}$ as $\operatorname{ord}_n a$. I did some experiments and observed that:

1. $\operatorname{ord}_{pq} a = \operatorname{ord}_p a \times \operatorname{ord}_q a$, where $p$ and $q$ are primes and $\gcd(a, p) = \gcd(a, q) = 1$
2. $\operatorname{ord}_{p^n} a = \operatorname{ord}_p a \times p^{n-1}$

Are those equalities true in general or I'm missing something and why? Are there any efficient algorithms to compute $\operatorname{ord}_n a$?

Answer 1

Note: I will note that when you talk about “cyclic subgroups of $\mathbb{Z}/n\mathbb{Z}$”, the obvious interpretation is that you are talking about the additive group and its additive subgroups. You should really be talking about the (multiplicative) subgroups of $(\mathbb{Z}/n\mathbb{Z})^*$, because $\mathbb{Z}/n\mathbb{Z}$ is not a group under multiplication.

Both your statements are incorrect.

For example, consider $2$ modulo $15=3\times 5$. The order of $2$ modulo $3$ is $2$; the order of $2$ modulo $5$ is $4$. So the order modulo $15$ is $4$, but your claim in $1$ is that the order “should be” $8$. The correct statement is:

• if $\gcd(a,pq)=\gcd(p,q)=1$, then $\mathrm{ord}_{pq}(a) = \mathrm{lcm}(\mathrm{ord}_p(a),\mathrm{ord}_q(a))$.

To see this, note that by the Chinese Remainder Theorem: $a^x\equiv 1\pmod{pq}$ if and only if $a^x\equiv 1\pmod{p}$ and $a^x\equiv 1\pmod{q}$, given that $\gcd(p,q)=1$. Thus, we need $x$ to be a multiple of $\mathrm{ord}_p(a)$ and of $\mathrm{ord}_q(a)$. But that does not mean that the order modulo $pq$ is the product of those two: it only needs to be a multiple of their least common multiple.

2 is also incorrect as written. Consider $a=1$, $p=3$, $n=2$. The order of $1$ modulo $9$ is 1; but you claim it should be $\mathrm{ord}_3(1)\times 3^{2-1} = 3$.

From Hensel’s Lemma, if the order of $a$ modulo $p^n$ is $k$, then exactly one of its $p$ lifts modulo $p^{n+1}$ (the numbers $a+kp^{n}$, $k=0,\ldots,p-1$) will still satisfy $x^{k+1}-x\equiv 0\pmod{p^{n+1}}$ (using this polynomial so that $f’(a)\not\equiv 0\pmod{p}$) and so have order at most $k$; and in particular, since it has order at least $k$, it will have order exactly $k$. So not every lift (in particular, not necessarily $a$) will have the order you want.

(You can verify this because not every lift of a primitive root modulo $p$ is a primitive root modulo $p^2$).