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)¹
2 = 2×(-1)²
3 = (-3)×(-1)³
4 = 4×(-1)⁴
…

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!×2^s. The s! cancels the s! on the left, and 2^s 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. The cyclic multiplicative group has order p^k-1, where k is even The discrete log of each integer is a multiple of p^k-1 over p-1. This is even, hence every integer is a square, including 2.

Quartic Residue

If -1 is a square mod p, is it also a fourth power? Only if p-1 is divisible by 8, that is, p = 1 mod 8. Similarly, -1 is an 8^th power iff p = 1 mod 16, and so on.

If p = 1 mod 8, is 2 a fourth power? We already know it's a square. Raise 2 to the (p-1)/4 and see if it is 1 or -1.

Review the equations above, from 1 to s, where s = (p-1)/2. If x is a square then -x is also a square. If x is a square then 2x is also a square. Throw out all the equations that involve nonsquares. Now there are s/2 equations left. Why? Because half the nonzero entries are squares, and these match up in pairs, x with -x; half ≤ s and half > s. Multiply them together and cancel terms, leaving a factor of 2 to the (p-1)/4, which is exactly what we want. This is equal to -1 to the sum(x) where x is a square and x ≤ s. 2 is a fourth power iff this sum is even.