What is the best known lower bound for: $\max_{2\leq i\leq p-1}(ord_n(i)) $?

Question

Given an in integer $n$, and let $p$ be its smallest prime divisor (you can assume that $p$ is very large ). Let $ord_n(i)$ denotes the order of $i$ as an element of $\Bbb Z_n^*$ the multiplicative group of $\Bbb Z_n$.

My question:

What is the best known lower bound for: $$\max_{2\leq i\leq p-1}(ord_n(i)) $$

A lower bound

For example it's clear that if $k=ord_n(2)$ then $$2^k>n$$ because $$2^k\equiv 1 \mod n $$

so as a lower bound we have $\log_2(n) \leq \max_{2\leq i\leq p-1}(ord_n(i))$ I'm looking for some references which discuss this problem.

Crossposted at MSE: https://math.stackexchange.com/questions/1222761

Answer 1

Your quantity is at least $p-1$ since the range contains a primitive root modulo $p$ and the order modulo $n$ is at least the order modulo $p$. I don't expect you'll be able to improve this much (depending on the relative sizes of $n$ and $p$). This is obviously best possible if $n=p$ but, if there are infinitely many primes $p$ with $2p-1$ prime you can take $n=p(2p-1)$ and your quantity is $2(p-1)$ so the lower bound is off by a factor of $2$.