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}$?
How can we show $ord_{p}n + 1 \le \frac{2}{\log 2}$?
-
1Is $p$ a prime? What are the range of values of $n$, and $x$? – 2012-03-08
-
0The inequality you are quoting looks incomplete. There is a missing symbol. – 2012-03-08
-
1see http://math.stackexchange.com/questions/118051/how-can-we-show-1ord-pn-le-2ord-pn-le-pord-pn-x by the same OP – 2012-03-08
-
0I changed it in both. Sorry... – 2012-03-08
-
1The 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
-
0Some 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
-
0Author of what? A number theory book, perhaps? Title? – 2012-03-09
1 Answers
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.