Multiplicative orders modulo divisors of the modulus

24 Views Asked by At

Is there a known description of the set of multiplicative orders of a fixed unit $a$ modulo all divisors of some modulus $n$, i.e. of $\text{ord}_d(a)$ with $d\mid n$? It is easy to see that it is a subset of the set of all divisors of $\text{ord}_n(a)$. Indeed, if $a^m\equiv1\pmod{n}$ then $a^m\equiv1\pmod{d}$ for any $d\mid n$. Since $\text{ord}_d(a)$ must divide any such $m$ by Lagrange's theorem, it follows that $\text{ord}_d(a)\mid\text{ord}_n(a)$.

But it is not always the entire set of all divisors. For example, when $n=p$ is prime, $\text{ord}_p(a)$ can be composite and have divisors other than itself and $1=\text{ord}_1(a)$. So which divisors of $\text{ord}_n(a)$ are realizable by some $d\mid n$? Is it ever all of them in non-trivial cases? This question comes up when describing cycles of certain permutations.