Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
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
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)} $$ –  user2468 Mar 8 '12 at 23:44
show 4 more comments

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
Thank you, J.D. ! –  VVV Mar 9 '12 at 1:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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