Modular Mathematics, -1 and 2 as Quadratic Residues

-1 and 2 as Quadratic Residues

To see if -1 is a square, raise it to the (p-1)/2 power.  The result is 1 only when (p-1)/2 is even.  Therefore -1 is a quadratic residue iff p = 1 mod 4.

Next consider [2\p].  Write the following series of equations.

1 = (-1)×(-1)1
2 = 2×(-1)2
3 = (-3)×(-1)3
4 = 4×(-1)4
…

Let s be half of p-1, and let the equations run from 1 to s.  Multiply the s equations together, hence the left side becomes s!.  The right side includes a 2 from the second equation, a 4 from the fourth equation, and so on.  Once we pass s, the right side still has the even numbers, but they are disguised as negative numbers.  Twice s shows up as -1 (first equation), twice (s-1) is -3 (third equation), and so on.  So the right side contains s!×2s.  The s! cancels the s! on the left, and 2s is the same as [2\p].  Finally, the right side includes (-1)1+2+…+s.  The exponent simplifies to s×(s+1)/2.  This is even when s is 3 or 4 mod 4, which means 2 is a quadratic residue iff p = 1 or 7 mod 8.  2 is the square of 6 mod 17, but it isn't the square of anything mod 13.

Finite Fields

These results generalize to a finite field F, having size w, where w is a power of p.  The multiplicative group of F is cyclic, of size w-1, and the halfway point is -1, and this is a square iff something exists a quarter of the way through.  In other words, w = 1 mod 4.

If 2 is a square mod p then it is a square in F.  Since p is 1 or 7 mod 8, the same is true of w, and we're in good shape.

If 2 is not a square, and p is 3 or 5 mod 8, let F have odd dimension over p, whence w is 3 or 5 mod 8.  Adjoin the square root of 2 and find an intermediate extension of dimension 2.  This has to be a factor of the dimension of F over p, and that is impossible.  Hence 2 is not a square.

Finally let F have even dimension over p.  Thus w is 1 or 7 mod 8.  Since the extension is galois, it includes the extension of dimension 2.  Restrict F to this extension.  The cyclic multiplicative group has order p2-1.  The discrete log of each integer is a multiple of p+1.  This is even, hence every integer is a square, including 2.