View Single Post
Old 2006-08-06, 10:08   #33
konrad127123
 
konrad127123's Avatar
 
Jun 2005

3×11 Posts
Default

Quote:
Originally Posted by geoff
I think I have found part of the answer to this: when n is odd, say n=2m+1, then 4*5^n-1 can be written as 5*x^2-y^2 where x=2*5^m and y=1, and according to a table I found in Guy, the primes with 5 as a quadratic residue are all -1,1 (mod 10).
Correct :). I will try to explain where this table comes from.

Suppose p and q are odd primes. All odd primes are either 1 or 3 (mod 4). The law of Quadratic reciprocity says:

(A)If at least one of p and q is 1 (mod 4) then x^2=p (mod q) has a solution if and only if x^2=q (mod p) has a solution (so either both or neither of these congruences has a solution).

(B)If both p and q are 3 (mod 4) then exactly one of x^2=p (mod q) and x^2=q (mod p) has a solution (this case isn't relevant in the above)

Now let's set q=5. 5=1 (mod 4), so case A applies. Let p be the prime we're trial dividing by. So by case (A) x^2=5 (mod p) will only have a solution if and only if x^2=p (mod 5) has a solution. Substituting in x=0,1,2,3,4 in turn, we find that x^2 (mod 5) must be 0, 1 or 4. So if x^2=5 (mod p) has a solution then x^2 = p (mod 5) has a solution, so p=0,1 or 4 (mod 5).

So x^2=5 (mod p) can only have a solution if p=0,1 or 4 (mod 5). The only prime of the form p=0 (mod 5) is p=5 (which obviously won't divide any number of the form 4*5^n-1). So the only primes left are ones of the form p=1 or 4 (mod 5).

Now let's look at p (mod 10). If p is 1 or 4 (mod 5), then p is 1, 4, 6 or 9 (mod p). If p=4 or 6 (mod 10) then p is even and not equal to 2, so it is not prime. Thus p=1 or 9 (mod 10).

So if x^2 =5 (mod p) has a solution, then p=1 or 4 (mod p), so p=1 or 9 (mod 10), so we only need to consider such primes.

Quote:
Originally Posted by geoff
I think the same idea (and the same table) can be used to speed up sieveing for the sequences 2*3^n-1, 5*6^n-1, 6*7^n-1, but I don't know how to work out the general case yet: Given k, what are the congruence classes of the primes with k as a quadratic residue?
If I remember correctly, a similar idea can be used for *all* sequences of the form k*b^n+/-c.Have a look at http://www.free-dc.org/forum/showthread.php?t=10262 (in particular look at post #6). It is written for base 2 Riesel's, but should be fairly easy to adapt to base 5. You would also need to read up on the Legendre symbol. (I can't remember off the top of my head if the Jacobi symbol is relevant here or not.)

If you have time, I recommend reading any good book on "Elementry Number Theory", which will cover such things.

Hope this helps :)
konrad127123 is offline   Reply With Quote