# Thread: An exponential proof and an algorithm

1. ## An exponential proof and an algorithm

Hey guys i'm looking to prove that if $\displaystyle N = a^b$ then we are sure that either $\displaystyle b \leq \log(N)$ either $\displaystyle 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 $\displaystyle N = a^b$ form).

What i've done is $\displaystyle 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 $\displaystyle b \leq \log(N)$ as a fact to prove that when N=1 if $\displaystyle b \leq \log(N)$ also applies then $\displaystyle 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 $\displaystyle N = a^b$ then we are sure that either $\displaystyle b \leq \log(N)$ either $\displaystyle 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 $\displaystyle N = a^b$ form).

What i've done is $\displaystyle 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 $\displaystyle b \leq \log(N)$ as a fact to prove that when N=1 if $\displaystyle b \leq \log(N)$ also applies then $\displaystyle 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 $\displaystyle N = a^b$ holds, while neither $\displaystyle b \le \log N$ nor $\displaystyle 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 $\displaystyle N = a^b$ holds, while neither $\displaystyle b \le \log N$ nor $\displaystyle 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, $\displaystyle N = a^b$ holds. however, $\displaystyle \log N \approx 0.301$, and so $\displaystyle 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 $\displaystyle N = a^b$ then we are sure that either $\displaystyle b \leq \log(N)$ either $\displaystyle 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 $\displaystyle N = a^b$ form).

What i've done is $\displaystyle 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 $\displaystyle b \leq \log(N)$ as a fact to prove that when N=1 if $\displaystyle b \leq \log(N)$ also applies then $\displaystyle 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