Let factored uniquely into primes, and let be an integer coprime to . If we denote by the multiplicative order of modulo then Euler’s theorem tells us that , so that . Can we do better?

Note that for each by Euler’s theorem. Hence

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

.

By the Chinese Remainder Theorem we can choose to be a primitive root modulo for simultaneously. Hence equality can be achieved in for any . Further, if one of the is and one is congruent to then the GCD in is exactly , so that equality is achieved in . So is the best uniform bound if , while if then is uniformly the best possible.