# Thread: An exponential proof and an algorithm

1. ## An exponential proof and an algorithm

Hey guys i'm looking to prove that if $N = a^b$ then we are sure that either $b \leq \log(N)$ either $N = 1$ is true, where a,b,N are all positive integers.
And using that (i suppose, but not necessarily), to create an algorithm that given an integer can verify whether it's a power (i mean it can be written in the $N = a^b$ form).

What i've done is $N = a^b \Rightarrow \log(N) = b\log(a)\Rightarrow b = \frac{\log(N)}{\log(a)} \leq \log(N)$ Provided that a!=1
Then used $b \leq \log(N)$ as a fact to prove that when N=1 if $b \leq \log(N)$ also applies then $b\leq0$ which is impossible since we know b>0

Is that correct?
Thanks!

2. Originally Posted by Barbas
Hey guys i'm looking to prove that if $N = a^b$ then we are sure that either $b \leq \log(N)$ either $N = 1$ is true, where a,b,N are all positive integers.
And using that (i suppose, but not necessarily), to create an algorithm that given an integer can verify whether it's a power (i mean it can be written in the $N = a^b$ form).

What i've done is $N = a^b \Rightarrow \log(N) = b\log(a)\Rightarrow b = \frac{\log(N)}{\log(a)} \leq \log(N)$ Provided that a!=1
Then used $b \leq \log(N)$ as a fact to prove that when N=1 if $b \leq \log(N)$ also applies then $b\leq0$ which is impossible since we know b>0

Is that correct?
Thanks!
are you sure you stated the problem correctly?

for consider N = a = 1/2 and b = 1. Then they are all positive integers and $N = a^b$ holds, while neither $b \le \log N$ nor $N = 1$ is true

3. Originally Posted by Jhevon
are you sure you stated the problem correctly?

for consider N = a = 1/2 and b = 1. Then they are all positive integers and $N = a^b$ holds, while neither $b \le \log N$ nor $N = 1$ is true
If i'm not mistaken 1/2 is not an integer

4. Originally Posted by Barbas
If i'm not mistaken 1/2 is not an integer
haha, yes, of course, you're right. don't know what i was thinking...well, yes i do, i was thinking of the log graph which is defined for non-integers.

in that case, consider N = a = 2 and b = 1.

then surely they are all positive integers now. wait, let me double check...yeah, positive integers. moreover, $N = a^b$ holds. however, $\log N \approx 0.301$, and so $b \le \log N$ is false, and so is the statement N = 1.

5. Sorry it took so long for me to get back with the events here in Greece. I don't know the professor is usually vague with his problems, maybe he meant a log of base 2?
Would the argument hold then?

6. Originally Posted by Barbas
Hey guys i'm looking to prove that if $N = a^b$ then we are sure that either $b \leq \log(N)$ either $N = 1$ is true, where a,b,N are all positive integers.
And using that (i suppose, but not necessarily), to create an algorithm that given an integer can verify whether it's a power (i mean it can be written in the $N = a^b$ form).

What i've done is $N = a^b \Rightarrow \log(N) = b\log(a)\Rightarrow b = \frac{\log(N)}{\log(a)} \leq \log(N)$ Provided that a!=1
Then used $b \leq \log(N)$ as a fact to prove that when N=1 if $b \leq \log(N)$ also applies then $b\leq0$ which is impossible since we know b>0

Is that correct?
Thanks!
For practical purposes this is incomprehensible.

CB

7. Yeah i guess, but it's the best i could do so far