## Theorem about distribution of squares mod p.

Expand Messages
• If p 1 is a prime equal to 3 mod 4, Then there are (p+1)/4 squares s mod p 0
Message 1 of 1 , Jul 14, 2009
If p > 1 is a prime equal to 3 mod 4,

Then there are (p+1)/4 squares s mod p

0 < = s < p,

such that (s-1) is also a square mod p

Proof:

Let p be prime = 3 mod 4.

1 is a square mod p.
1 - 1 = 0 is a square mod p.

1**2 - 0**2 = ( 1 - 0) * (1 - 0) = 1.
(p-1)**2 - 0**2 = 1 mod p

((p-1) - 0) * ( (p-1) + 0) = 1 mod p

There are p-1 - 2 = p-3 remaining pairs (j,k)
in mod p
such that

j * k = 1 mod p.

( (j + k)/2) **2 - ( (j-k) /2)**2 = 1

Define the following to be equivalent pairs,

(j,k),(-j,-k), (k,j), (-k,-j).

What makes them equivalent is that all four of these pairs lead to the same
square difference

( (j + k)/2) **2 - ( (j-k) /2)**2 = 1

Thus the number of remaining "consecutive" squares mod p is (p - 3) / 4.

A similar proof shows that the number of

"consecutive" squares mod p where p is equal to 1 mod 4,

is (p+3)/4.

Kermit Rose
Your message has been successfully submitted and would be delivered to recipients shortly.