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>



What is the best known lower bound for: $\max_{2\leq i\leq p-1}(ord_n(i)) $?
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$. 


