# A bound on the multiplicative order

Let $n=p_1^{a_1}\cdots p_k^{a_k}$ factored uniquely into primes, and let $a$ be an integer coprime to $n$. If we denote by $\hbox{ord}_na$ the multiplicative order of $a$ modulo $n$ then Euler’s theorem tells us that $\hbox{ord}_na\mid\phi(n)$, so that $\hbox{ord}_na\le\phi(n)$. Can we do better?

Note that $a^{p_i^{a_i-1}(p_i-1)}\equiv 1\pmod{p_i^{a_i}}$ for each $i$ by Euler’s theorem. Hence

(*)\qquad\qquad\begin{aligned}\hbox{ord}_na&\le [p_1^{a_1-1}(p_1-1),\dots,p_k^{a_k-1}(p_k-1)]\\ &=\frac{\phi(n)}{(p_1^{a_1-1}(p_1-1),\dots,p_k^{a_k-1}(p_k-1))^{k-1}}\end{aligned}

using a result from this post. Now if $2\parallel n$, then the GCD on the right-hand side is equal to $1$. Otherwise $2$ divides the GCD, so that

$(**)\qquad\qquad\qquad\qquad\displaystyle\hbox{ord}_na\le\frac{\phi(n)}{2^{k-1}}=\frac{\phi(n)}{2^{\omega(n)-1}}$.

By the Chinese Remainder Theorem we can choose $a$ to be a primitive root modulo $p_i^{a_i}$ for $i=1,\dots,k$ simultaneously. Hence equality can be achieved in $(*)$ for any $n$. Further, if one of the $p_i$ is $2$ and one is congruent to $3\pmod 4$ then the GCD in $(*)$ is exactly $2$, so that equality is achieved in $(**)$. So $(**)$ is the best uniform bound if $n\not\equiv 2\pmod 4$, while if $n\equiv 2\pmod 4$ then $\hbox{ord}_na\le \phi(n)$ is uniformly the best possible.