Re: Quadratic residue method for finding primes

In article <124gm0rbklunf96@corp.supernews.com>,
Bob Terwilliger <RobertUnderdunkTerwilliger@noneOfYourBusiness.com> wrote:

   [.snip.]

>> What I have found is a simple to the point of trivial method for using
>> quadratic residues to greatly increase the odds of finding prime
>> numbers, with the primary idea being a method to quickly find very
>> large primes.
>>
>> p^2 - 2
>>
>> is what I started with where for a number to be a factor of that it
>> must be a prime with a quadratic residue of 2 or decomposable into
>> primes with 2 as a quadratic residue, where the first is 7.
>
>Quadratic residue modulo what?

Instead of "with a quadratic residue of 2", you should read "which has
2 as a quadratic residue".

In other words: if q is a prime that divides p^2-2, where p is an odd
prime, then 2 is a quadratic residue modulo q. This, of course, is
simply noting that p^2 - 2 = 0 (mod q), so p^2=2 (mod q), so 2 is a
quadratic residue modulo q.

>I think you're saying that if q is a
>prime factor of p^2 - 2, then x^2 == 2 mod q is solvable for some
>integer x, is this correct? I'm not sure what you mean by the second
>part: "... or decomposable into primes with 2 as a quadratic
>residue".

p^2 - 2 will either be (i) a prime which has 2 as a quadratic residue;
or (ii) composite, and all its prime factors will have 2 as a
quadratic residue (i.e., if q is any prime factor of p^2-2, then 2 is
a quadratic residue modulo q).

>Do you mean that for at least one such prime, say q1, 2 is a quadratic
>residue mod q1?

All primes dividing p^2-2 will have 2 as a quadratic residue. In fact,
if m is odd, then all integers n dividing m^2-2 will have 2 as a
quadratic residue (i.e., if n divides m^2-2, then 2 is a quadratic
residue modulo n; we need m odd so that (2,n)=1).

Note that we know exactly which primes have 2 as a quadratic residue:
namely, those which are congruent to 1 or -1 modulo 8. Likewise, if we
replace 2 with any prime r, then we can figure out exactly which
primes have r as a quadratic residue by the use of Quadratic
Reciprocity; and they will all lie in certain arithmetic progressions
modulo r or modulo 4r (depending on whether r is congruent to 1 modulo
4 or to 3 modulo 4).

-- 
======================================================================
"It's not denial. I'm just very selective about
 what I accept as reality."
    --- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
magidin@math.berkeley.edu