Quadratic Character

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

Background theory about polynomials

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

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

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


Theorem A degree nn polynomial has at most nn roots

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

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

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

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

The character of -1 mod 4k+1

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

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

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

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

The character of -3 mod 3k+1

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

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

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

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

The character of 2 mod 8k+1

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

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

x4k+1(x2k+1)22x2k0(modp)x^{4k} + 1 \equiv (x^{2k} + 1)^2 - 2x^{2k} \equiv 0 \,\,(\text{mod}\, p)

and thus (setting yy to be the inverse of xx)

(yk(x2k+1))22(modp)(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+78k+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 α4=1\alpha^4 = -1 and define y=α+α1y = \alpha + \alpha^{-1} so that y2=2y^2 = 2.

Since yp=αp+αp=α7+α7=α1+α=yy^p = \alpha^p + \alpha^{-p} = \alpha^7 + \alpha^{-7} = \alpha^{-1} + \alpha = y we see that yy lies in Fp\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.