0

Let's say I give you a number: 2985984, which is equal to $x^y$, where both $x$ and $y$ are integers. How would you find $x$ and $y$ (hint: the answer is 12^6)?

Now, let's say I'll say that $x$ is 12. then you can write:

$12^y = 2985984$.

$log(12^y) = log(2985984)$

$y\times log(12) = log(2985984)$

$y = \frac{log(2985984)}{log(12)}$

$y=6$

A more general form would be:

$y = \frac{log(2985984)}{log(x)}$

How would I find which integer values of $x$ and $y$ would solve this equation?

Charles Shiller
  • 103
  • This should be loosely equivalent to deciding if an integer is prime (consider the worst case scenario), and so probably proportional to $\sqrt{n}$ in computation time. – David P Apr 22 '18 at 06:27
  • @DavidPeterson: While screening out perfect powers is a step in determining if a number is prime, it seems to be an easier problem. See the description of the AKS primality test. – hardmath Apr 22 '18 at 06:38

1 Answers1

1

The first step would be to factor $z = 2985984 = 2^{12}3^6.$ In particular, note that $$z = \left(2^2 \cdot 3 \right)^6 = \left(2^4 3^2\right)^3 = \left(2^63^3\right)^2 = \left(2^{12}3^6\right)^1.$$ In general, for $z = p_1^{e_1}p_2^{e_2}p_3^{e_3} \cdots$ for primes $p_i$ and positive integers $e_i$, all $y \mid \gcd (e_1,e_2,e_3,\dots)$ will work. From here, we can find $x = \sqrt [y] z,$ and if $y$ is even $x = - \sqrt [y] z$ also works.

Preston Fu
  • 94