Re: Quadratic residue method for finding primes

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! Thanks for the clarification Arturo... this is so
obvious!

>
>
>
>>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).

Agreed, just like you said above (nice).

>
>
>>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).

Yes, as you say, m will be a solution... i.e., n | m^2 - 2 -> m^2 == 2
mod n.

>
> 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? I'm starting to sense analytic
number theory on the horizon!
Received on Mon May 1 02:03:34 2006