View Single Post
2009-04-23, 19:33   #3
Uncwilly
6809 > 6502

"""""""""""""""""""
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.
Quote:
 Originally Posted by Dr. Silverman 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 once) 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.

Thanks