Quote:
Originally Posted by wblipp
Depending on the source of the number, you may or may not know whether the number has small factors. If the number might have small factors, do some trial factoring before applying the test method described above. If you find any factors, the power must be a divisor of the gcd of the exponents of the trial factors.
I believe Dario Alpern's Java factoring applet uses this method when checking if a number is a^{n} +/ 1
William

Good point! For example, one knows that numbers of the form a^n+1 are never perfect powers (except in the cases 2^3+1 and 3^21).