Loading ...
Sorry, an error occurred while loading the content.

Theorem about distribution of squares mod p.

Expand Messages
  • Kermit Rose
    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 6:28 PM
    • 0 Attachment
      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.