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

  • 1
    Is $p$ a prime? What are the range of values of $n$, and $x$?2012-03-08
  • 0
    The inequality you are quoting looks incomplete. There is a missing symbol.2012-03-08
  • 1
    see http://math.stackexchange.com/questions/118051/how-can-we-show-1ord-pn-le-2ord-pn-le-pord-pn-x by the same OP2012-03-08
  • 0
    I changed it in both. Sorry...2012-03-08
  • 1
    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)} $$2012-03-08
  • 0
    Some of my $<$ should be $\le$ and vice versa..2012-03-08
  • 0
    @J.D. Why do you put $0 < n < p$ ?2012-03-08
  • 0
    @VVV order of an element $n$ in a group $\mathbb{Z}_p$. Check out the first few lines in this [PDF lecture note](http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/order.pdf).2012-03-09
  • 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.