Quadratic Character

In this post I want to write a bit about the following:

• Let $p = 4k+1$ then $-1$ is a square mod $p$.
• Let $p = 3k+1$ then $-3$ is a square mod $p$.
• Let $p = 8k \pm 1$ then $2$ is a square mod $p$.

Background theory about polynomials

First we need a few generic theorems about polynomials, We'll apply them in $\mathbb Z$, ${\mathbb F}_p$ and it's algebraic closure.

Theorem Let $p$ be a polynomial with root $p(\alpha) = 0$ then $(x - \alpha) | p(x)$.

Proof: This can be seen using the Euclidean division algorithm: $p(x) = Q(x) (x - \alpha) + R(x)$ with $R(x)$ has degree 0: it's a constant but it must be zero.

Consequences

• $x^2 - 1$ has roots $1$ an $-1$ so equals $(x - 1)(x + 1)$
• $x^3 - 1$ has a root $x=1$ so dividing out $x-1$ we find it equals $(x - 1)(x^2 + x + 1)$
• $x^4 - 1$ equals $(x^2)^2 - 1 = (x^2 - 1)(x^2 + 1) = (x - 1)(x + 1)(x^2 + 1)$

Theorem A degree $n$ polynomial has at most $n$ roots

Proof: each root may be factored out to produce a polynomial with lower degree.

Theorem In a finite field $\mathbb F_{p^r}$, $\alpha^p = \alpha$ implies that $\alpha \in \mathbb F_p$.

Proof: By Fermats little theorem we know $\alpha^{p-1} = 1$ holds for all $p-1$ nonzero elements of $\mathbb F_p$, so it cannot hold for any other elements.

Lemma In a finite field $(x + y)^p = x^p + y^p$.

The character of -1 mod 4k+1

Let $p = 4k+1$ then by Fermats little theorem $x^{4k} \equiv 1 \,\,(\text{mod}\, p)$ has $4k$ roots and factors as $((x^k)^2 - 1)((x^k)^2 + 1) \equiv 0 \,\,(\text{mod}\, p)$ and this equation is solved if one of

• $(x^k)^2 - 1 \equiv 0 \,\,(\text{mod}\, p)$
• $(x^k)^2 + 1 \equiv 0 \,\,(\text{mod}\, p)$

holds. Since they are of degree $2k$ each of them is solved half the time.

This leads to an "randomized" algorithm for finding a square root of -1 mod $p$: Just pick a random number $x$ and $x^k$ will be a square root of -1 with probability 1/2.

You can show that there is no solution mod $4k+3$ by checking congruences.

The character of -3 mod 3k+1

Let $p = 3k+1$, by Fermats little theorem $x^{3k} \equiv 1 \,\,(\text{mod}\, p)$ and this factors as

• $x^k - 1 \equiv 0 \,\,(\text{mod}\, p)$
• $x^{2k} + x^k + 1 \equiv 0 \,\,(\text{mod}\, p)$

the second equation being solved 2/3s of the time, and it leads to a square root of -3 since $4 \cdot (x^{2k} + x^k + 1) \equiv (2x^k+1)^2 + 3 \equiv 0 \,\,(\text{mod}\, p)$ hence

$(2x^k+1)^2 \equiv -3 \,\,(\text{mod}\, p)$

You can show that there is no solution mod $3k+2$ by checking congruences.

The character of 2 mod 8k+1

Let $8k + 1$, then similar to before we reach

• $x^{2k} - 1 \equiv 0 \,\,(\text{mod}\, p)$
• $x^{2k} + 1 \equiv 0 \,\,(\text{mod}\, p)$
• $x^{4k} + 1 \equiv 0 \,\,(\text{mod}\, p)$

the last of which is solved 1/2 the time:

$x^{4k} + 1 \equiv (x^{2k} + 1)^2 - 2x^{2k} \equiv 0 \,\,(\text{mod}\, p)$

and thus (setting $y$ to be the inverse of $x$)

$(y^k \cdot (x^{2k} + 1))^2 \equiv 2 \,\,(\text{mod}\, p)$

The character of 2 mod 8k+7

2 is also a square mod $8k+7$ but we can't show this in the same sort of elementary way. The proof from Serre - Course in Arithemtic uses the algebraic closure of the finite field to work with 8th roots of unity:

Let $\alpha$ be a primitive 8th root of unity so that $\alpha^4 = -1$ and define $y = \alpha + \alpha^{-1}$ so that $y^2 = 2$.

Since $y^p = \alpha^p + \alpha^{-p} = \alpha^7 + \alpha^{-7} = \alpha^{-1} + \alpha = y$ we see that $y$ lies in $\mathbb F_p$.

I'm not sure how this last calculation could be used as an algorithm to find square roots of 2 mod 8k+7.