View Single Post
Old 2009-04-23, 19:33   #3
6809 > 6502
Uncwilly's Avatar
Aug 2003
101×103 Posts

22B216 Posts

Realize that I am not the OP. And that I am not asking the Dr. to do this, unless he wishes to.
Originally Posted by Dr. Silverman View Post
Let a_i = N mod p_i for p_i = 2,3,5,7,11.....
up to some selected bound.

If N is a kth power, then it will be a kth power mod each of the primes.
If it fails any prime, then it is not a k'th power. Or one could check
if it is a kth power mod 2*3*5*7*11.... etc. (i.e. check all primes at

If it is a kth power mod each prime, then we suspect that it actually
is a kth power.
Could someone show an example of this, with a real pair of numbers (say, 62748517 =13^7 and 62748571 [a random similar numbr]). I kinda get lost in the highlighted section. I think that I can grasp most of the rest and looked briefly at Newton's method (successive approx.) and get that.

Uncwilly is offline   Reply With Quote