2
$\begingroup$

Are there any quick modulus methods to check if a number could be a perfect power (4, 5, 6)? Preferably binary methods that could be extended to higher powers.

For example, a perfect fourth power has to be $0, 1 \pmod{16}$ from a square number being $0, 1 \pmod 4$. Also, a perfect sixth power has to be $0,1 \pmod{8}$.

Other than something very simple, a few iterations of Newton's method converges very quickly.

$\endgroup$
1
$\begingroup$

I am copying Jeremy Teitelbaum's answer here.


See the paper by Bernstein, Lenstra, and Pila: “Detecting Perfect Powers by Factoring into Coprimes”, Mathematics of Computation, Volume 76, #257, January 2007, pp. 385–388.

From the abstract:

This paper presents an algorithm that, given an integer $n>1$, finds the largest $k$ such that $n$ is a $k$th power.

The algorithm runs in time $\log(n)(\log\log(n))^{O(1)}$.

$\endgroup$
  • $\begingroup$ This is good, but I was looking for something simpler. Something that could be done just to reject obvious cases $\endgroup$ – qwr Jan 22 '15 at 4:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.