View Single Post
Old 2009-04-24, 00:01   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by fivemack View Post
2^25 < 62748571 < 2^26, and it's obviously not a power of two, so if it is a kth power we have k<26.

log(62748571)/log(3) = 16.34, so it's not a power of three; log(62748571)/log(5) = 11.15, so it's not a power of five;
log(62748571)/log(7) = 9.23.

So, if 62748571 is a kth power, k is 2, 3, 5 or 7.

62748571 is congruent to 6 mod 11, but the squares mod 11 are 0, 1, 3, 4, 5 and 9, so k is not 2. The fifth powers mod 11 are 0, 1 and 10, so k is not 5 either.

62748571 mod 7 = 4, but the cubes mod 7 are 0, 1 and 6, so k is not 3.

62748571 mod 29 = 24, but the 7th powers mod 29 are 0, 1, 12, 17 and 28, so k is not 7.

So 62748571 is not an exact power.

By the same set of logs, we know that if n=62748517 is a kth power, k is 2, 3, 5 or 7. n is 7 mod 11, so k is not 2 or 5; n mod 7 is 6 so it could be a cube, but the cubes mod 19 are 0, 1, 7, 8, 11, 12 and 18, and n%19=10.

So k could only be 7, and indeed exp(log(62748517)/7) is 13.00000 and 13^7 = 62748517.

Sure. But for really big integers you would need a high precision
logarithm function, and writing such is difficult (and slow). So when
you suspect it might be a kth power, compute floor(N^1/k). This
can be done using only integer arithmetic via Newton's method.

The sample values of N given here. really do not show how powerful
looking at N modulo small primes really is. Try it with N near 2^1024, for
example.
R.D. Silverman is offline   Reply With Quote