What is the largest multiplicative order of an arbitrary natural number $x$ modulo a set of primes?

69 Views Asked by At

A set of primes is given that includes all primes $p$ such that $q_1 \le p \le q_2$. Then a natural $x$ is given that is less than $q_2$. Then all of the multiplicative orders of $x$ modulo the various $p$s are tallied, with the exceptions that if $p | x$, that is that $p$ divides $x$ is not tallied.

This question is to try to get an idea of the distribution of the multiplicative orders for varying $q_2$, with $p$ growing with $q_2$.

In my math software, I looked at the multiplicative order of $10$ modulo the $100$th prime to the $100,000$th prime. It showed that there are $6$ primes where $10$ has a multiplicative order of $1620$. All other orders had less hits.

Then I looked at $1000$ and $1000000$ modulo the same primes. $1000$ had multiplicative order $1060$ for 8 different primes, and $1,000,000$ also had multiplicative order $530$ for 8 different primes.

So I'm wondering if the (largest) multiplicative order must grow as $x$ and the primes grow. I'm hoping that this is true, and that someone can put some sort of lower bounds on the growth, stating that they must grow at least so fast.