Distribution of squares mod p


I was asked the following and had no idea.

For p an odd prime, how many squares are congruent (mod p)
to a "positive" residue -- one of {1, 2, 3, ..., (p-1)/2 } ?

When p = 1 mod 4, the answer is "exactly half", since if x is
a square, so is -x .

What about when p = 3 mod 4 ? Is it true that there are more
"positive" squares than "negative" ones?

(Arguably the small positive numbers have a better "chance" to be
squares mod p because the residue itself is more likely to be square
when in the interval [0, (p-1)/2] than in the interval
[(p-1)/2 , p], but to the extent that it means anything at all,
it can't give more than an O(sqrt(p)) advantage to the smaller,
i.e. "positive", residues.)

A spot check of the literature didn't turn up anything useful, but
I'm sure I haven't got useful search terms.

I've checked several tens of thousands of small examples, and
sure enough the small squares are always more numerous than the
large ones. But famously we know that small data can be misleading
when comparing primes = 1 mod 4 and primes = 3 mod 4 ...

dave
.

Relevant Pages

  • Least squares
    ... To solve a least squares problem, ... this means that the magnitude of the residue is ...
    (sci.math)
  • Re: Distribution of squares mod p
    ... For p an odd prime, how many squares are congruent ... It also says that no direct proof (that is, ...
    (sci.math)
  • Re: Number theory problem
    ... of positive divisors which are congruent to 3 mod 4. ... inequality is strict if and only if n can be written as the sum of two ... n is a sum of two squares if and only if for every prime p ...
    (sci.math)
  • Re: Algebraic Number Theory Question (easy?)
    ... > understanding this brief outline of why prime numbers p congruent to 1 ... > mod 4 are the sums of two squares: ...
    (sci.math)
  • Re: sums of squares mod (p=4n+3)
    ... any prime factor congruent to 3 mod 4 present with even multiplicity. ... but actually I said *distinct* positive squares. ... interested to see a sum of two distinct positive squares divisible by 361. ... because of unique factorization in the Gaussian ...
    (sci.math)