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


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.