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.

Advertisements

Leave a comment

Filed under Number theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s