2
$\begingroup$

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}$?

  • 0
    Author of what? A number theory book, perhaps? Title?2012-03-09

1 Answers 1

1

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

Again, lots of details need to be worked out, and left as an exercise.