# How can we show $ord_{p}n + 1 \le \frac{2}{\log 2}$?

How can we show that $ord_{p}n + 1 \le 1 + \frac{log n}{log p} \le 1+\frac{log n}{log 2} \le \frac{2 log n}{\log 2}$ for $p<2^{x}$ prime ( the author doesn't explicitly say this, but I assume it because p was used for primes all along), $n\ge 2 \in \mathbb{N}$; $x>0 \in \mathbb{R}$?

-
Is $p$ a prime? What are the range of values of $n$, and $x$? –  user2468 Mar 8 '12 at 23:34
The inequality you are quoting looks incomplete. There is a missing symbol. –  André Nicolas Mar 8 '12 at 23:37
see math.stackexchange.com/questions/118051/… by the same OP –  Will Jagy Mar 8 '12 at 23:40
I changed it in both. Sorry... –  VVV Mar 8 '12 at 23:43
The fraction should be $\frac{\log p}{\log n}$. For any $0 < n < p$, if $w = \operatorname{ord}_p n$, then $n^w \equiv 1 \pmod p$, and hence $$n^w = 1 + kp$$ for some integer $k > 0$.Taking $\log$, we have $$w \log n = \log(kp) = \log(k) + \log(p) \le \log(p)$$ Hence $$\operatorname{ord}_p n = w < \frac{\log(p)}{\log(n)}$$ –  user2468 Mar 8 '12 at 23:44

Here is a hint based on the assumption that the fraction is $\frac{\log p}{\log n}$. Details need to be checked and worked out.
For any $1 < n < p$, if $w = \operatorname{ord}_p n$, then $n^w \equiv 1 \pmod p$, and hence $$n^w = 1 + kp$$ for some integer $k > 0$.Taking $\log$, we have $$w \log n = \log(kp) = \log(k) + \log(p) \le \log(p)$$ Hence $$\operatorname{ord}_p n = w < \frac{\log(p)}{\log(n)}.$$ This allows you to prove the first $\le$.
Now since $p < 2^x$, then $\log p < x \log 2$. If $x > 0$ then the second inequality follows. The third inequality follows from the fact that $\frac{\log(p)}{\log(n)} \ge 1$, and hence $1 + \frac{\log(p)}{\log(n)} \le \frac{\log(p)}{\log(n)} \ge 1$.