View Single Post
Old 2009-04-24, 02:48   #9
Zeta-Flux's Avatar
May 2003

7·13·17 Posts

Originally Posted by wblipp View Post
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 an +/- 1

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^2-1).
Zeta-Flux is offline   Reply With Quote