Re: Another Quad. Residue question

"Nobody"
> > 1) Is there a good comprehensive source on
> > quadratic residues?
> > 2) Is it true that given a prime P, then there
> > there is between P and
> > 2P an (even?) integer for which P is not a
> > P is not a quadratic
> > residue?
> > 3) If 2) is true, can such an integer be
> > ger be expressed as a function
> > of P.
> >
> > Thanks much for information.
>
> If p=3 (mod 4), we can pick p+4.
> (Pick p+1 if you want an even integer.)
>
> If p=1 (mod 4), we can pick p+k,
> where k is any quadratic non-residue mod p.
> (Pick an odd q.n-r if you want an even integer.)
He wants a quadratic *non*-residue. Alas there is no
known algorithm of any value. Even the very elementary
proof that nonsquares exist, and are one-to-one with the
squares, is indirect: there are (p-1)/2 squares (omitting
zero), and the rest are nonsquares. But how to find
a nonsquare without effectively finding *all* the
squares? Nobody knows.
LH


.

Relevant Pages

  • Re: arithmetic progressions containing squares?
    ... by showing that squares can only be congruent ... Check on quadratic residues. ... I do not claim that these views are those of the Statistics Department or of Purdue University. ...
    (sci.math)
  • Re: Another Quad. Residue question
    ... >>> quadratic residues? ... >>> ger be expressed as a function ... and the rest are nonsquares. ... > a nonsquare without effectively finding *all* the ...
    (sci.math)