View Single Post
Old 2006-07-29, 23:50   #30
geoff's Avatar
Mar 2003
New Zealand

115710 Posts

Originally Posted by geoff
For the sequence 4*5^n-1, can anyone explain why all the factors end in 1 or 9 when n is odd?
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).

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?
geoff is offline   Reply With Quote