$1+ord_{p}n \le 2^{ord_{p}n} \le p^{(ord_{p}n)/x}$ for $p> 2^{x},n\ge 2 \in \mathbb{N}$; $x>0 \in \mathbb{R}$ It was written here that this is clearly the case; I don't see it. Does somebody see it and cares to explain?
How can we show $1+ord_{p}n \le 2^{ord_{p}n} \le p^{(ord_{p}n)/x}$
3
$\begingroup$
number-theory
1 Answers
2
The first inequality is a consequence of the fact that if $k$ is a positive integer, then $1+k \le 2^k$. Just take $k=\text{ord}_p(n)$.
If you wanted to, you could prove that $1+k\le 2^k$ by induction on $k$. But there is no need, the result is clear. At $k=1$ we have equality, but then $2^k$ grows much faster than $1+k$.
For the second inequality, take the logarithm of both sides. It is cleanest to use logarithms to the base $2$. So we want to prove that $\text{ord}_p(n) \le \frac{\text{ord}_p(n)}{x}\log_2(p).$ Since $p>2^x$, we have $\log_2(p)>x$, and the result follows.