$N = a^{b}$ is $L$ bits long, for some integers $a \geq 1, b \geq 2$. Show that $b \leq L$.

Question

Suppose $N = a^{b}$ for some integers $a \geq 1$ and $b \geq 2$ and $N$ is $L$ bits long.

Show that $b$, if it exists, satisfies $b \leq L$.

Note: as far as I kwon, for positive integers I can use: $L = \left\lceil \log_{2}{N} \right\rceil$.

Answer 1

I think you need $a\ge 2$, otherwise $N=1^2$ is a counterexample. If $a\ge 2$ then we have

$N \le 2^L \Rightarrow \log_2(N) \le L$

$\log_a(N) \le \log_2(N)\text{ since } a \ge 2$

$\Rightarrow \log_a(N) \le \log_2(N) \le L$

$\Rightarrow b \le L$