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$.

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)$

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$.

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)$

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.

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)$

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

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

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)$

$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)$

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.