Re: Quadratic residue method for finding primes

Arturo Magidin wrote:
> 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.
>

Yeah, like I said, old, boring to me, mathematics.

Nothing new in there.

The odd thing is that given the realization that you are getting fewer
primes by looking at a specific quadratic residue, no one bothered to
use quadratic residues--unless someone can come back with info that
they did--to search for primes!

It's a bizarre miss.

n^2 - r

where r is a non-square natural is just such a natural way to mask out
primes that you'd think that what I'm talking about now would be common
info, and routinely used by people looking for large primes.

Oh, but here's where it just gets truly bizarre on an absurd scale, as
playing with these ideas, I almost immediately could relate quadratic
residues to the Goldbach conjecture!!!

Some of you may not yet comprehend that I am labeled a crackpot not
because I don't have good ideas but because math people are political.

So it's like they're Republicans, and I'm not wanted as part of their
political party, so it doesn't matter what I discover or how good my
ideas actually are, as by definition, I am out with them.

That's why politics is such a nasty field.

Let's see though if the nasty people can ignore that relation to
Goldbach and get away with it.

Believe it or not, I think they WILL try as they don't actually give a
damn about mathematics.

They are bad people.

James Harris
Received on Mon May 1 02:03:40 2006