Re: Quadratic Residue -- proof or example

In article <Xns964782677BFA9goddardb@xxxxxxxxxxxxxx>,
Bart Goddard <goddardbe@xxxxxxxxxxxx> wrote:
>mathedman@xxxxxxxxxxxxxxx wrote:
>
>>
>> Given: P is a prime of the form 8k+1.
>> Prove: P cannot be a quadratic residue of both P+3 and P+7
>>
>> (else, give a counter example)
>>
>
>I think P=1129 is a counter example.

P+3 = 1132 = 4*283. Since -3 is a quadratic residue modulo 4, P is a
quadratic residue modulo P+3 if and only if -3 is a quadratic residue
mod 283; using the Legendre symbol we have:

(-3/283) = (-1/283)(3/283)
= (-1)(-1)(283/3)
= (283/3) = (1/3) = 1.

P+7 = 1136 = 16*71.

1129 = 9 (mod 16), hence a quadratic residue. And

(1129/71) = (-7/71) = (-1/71)(7/71)
= (-1)(-1)(71/7)
= (1/7) = 1.

So 1129 is a quadratic residue modulo both 1132 and 1136.




--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================

Arturo Magidin
magidin@xxxxxxxxxxxxxxxxx

.

Relevant Pages

  • Re: Quadratic residue method for finding primes
    ... quadratic residues to greatly increase the odds of finding prime ... primes with 2 as a quadratic residue, ... if q is a prime that divides p^2-2, where p is an odd ... then 2 is a quadratic residue modulo q. ...
    (sci.crypt)
  • Re: Quadratic residue method for finding primes
    ... Arturo Magidin wrote: ... primes with 2 as a quadratic residue, ... if q is a prime that divides p^2-2, where p is an odd ... then 2 is a quadratic residue modulo q. ...
    (sci.crypt)
  • Re: Quadratic residue method for finding primes
    ... primes with 2 as a quadratic residue, ... if q is a prime that divides p^2-2, where p is an odd ... then 2 is a quadratic residue modulo q. ... those which are congruent to 1 or -1 modulo 8. ...
    (sci.crypt)
  • Re: Quadratic residue method for finding primes
    ... What I have found is a simple to the point of trivial method for using ... primes with 2 as a quadratic residue, ... Usually when one talks about quadratic residues, it's in relation to some modulus, like, 2 is a quadratic residue modulo q. ... go up the distribution, so it's like a shifted prime distribution, ...
    (sci.crypt)