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

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 references which discuss this problem.

Crossposted at MO: https://mathoverflow.net/questions/202362

• I assume $p$ is a prime divisor? – Gregory Grant Apr 6 '15 at 19:12
• yes it's the smallest prime divisor of $n$ – Elaqqad Apr 6 '15 at 19:17