Re: Quadratic residue method for finding primes

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

>Arturo Magidin wrote:
>> 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.
>
>Yikes... that's easy!

Isn't it amazing how standard nomenclature and notation, which has
been developed (in this particular area) over centuries can help make
such things easy, rather than harder? (-;

    [.snip.]

>> 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).
>>
>
>Yes, isn't this a result of Dirichlet?

No, it goes back further (though not much). It is an easy consequence
of Quadratic Reciprocity, and Euler had already conjectured as much
(at the same time as he conjectured Quadratic Reciprocity). The result
is the following, which is in fact equivalent to QR:

   Theorem. Let q be a fixed positive odd prime, and let p range over
   the odd positive primes different from q. Every such p can be
   uniquely represented in exactly one of the two forms:

        p = 4qk +/- a with k an integer, 0 < a < 4q, a=1 (mod 4)

   Under this notation, (q/p) = (a/q) (Legendre's symbol). Thus, the
   p for which q is a quadratic residue are exactly those p which are
   congruent to a or -a modulo 4q, with 0<a<4q, a=1 (mod 4), and
   (a/q)=1. These a's are given by the smallest positive remainders
   moudlo 4q of the odd squares 1^2, 3^2, ... , (q-2)^2.

For example, say you want to know which primes have 17 as a quadratic
residue. Setting aside 2 and 17, take p. Since 17=1 (mod 4), it
follows that (17/p) = (p/17). Thus, they are precisely the primes
which are congruent to quadratic residues of 17, modulo 17. The
quadratic residues modulo 17 are 1, -1, 2, -2, 4, -4, 8, and -8. So p
has 17 as a quadratic residue if and only if p = 1, -1, 2, -2, 4, -4,
8, or -8 (mod 17).

If you do this with 19, you will have to divide in cases, depending on
whether p=1 (mod 4) (in which case (19/p) = (p/19); or whether p=3
(mod 4) in which case (19/p) = -(p/19). This gives you certain
congruences modulo 4*19=76.
    
>I'm starting to sense analytic number theory on the horizon!

A bit, perhaps, in the proof that there are infinitely many primes in
each of these arithmetic progressions (Dirichlet's famous theorem of
Primes in Arithmetic Progressions, probably what you were thinking of
above). But this is all painfully elementary. My undergraduate
students, taking their first "Intro to Number Theory" course (for
most, only their second formal course involving proofs) can do this,
and did it for their midterm last week in fact.

-- 
======================================================================
"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