# Quadratic Reciprocity, Galois Theory, Elliptic Curves

Motivation

Where ${p}$ and ${q}$ are distinct odd primes, there exists a mysterious relationship between solutions of ${x^2=q}$ in ${\mathbb{F}_p}$ and ${x^2=p}$ in ${\mathbb{F}_q}$. This quadratic reciprocity is but the tip of the giant iceberg of reciprocity laws. Quadratic reciprocity is related closely to Galois representations.

The variety defined by equation ${x^2-a=0}$ usually will have either two solutions or none, depending on whether ${a}$ is a square in the number system of ${x}$. For instance, since ${1}$ is a square in all number systems, the variety for ${x^2-1=0}$ is

$\displaystyle S(\mathbb{Z})=S(\mathbb{Q})=S(\mathbb{R})=S(\mathbb{C})=\ldots =\{1, -1\}$

The variety for equation ${x^2+1=0}$ is

$\displaystyle S(\mathbb{Z})=S(\mathbb{Q})=S(\mathbb{R})=S(\mathbb{F}_3)=S(\mathbb{F}_7)=S(\mathbb{F}_{11})=\emptyset$

$\displaystyle S(\mathbb{C})=\{i, -i\} \ \ \ \ S(\mathbb{F}_5)=\{2, 3\} \ \ \ \ S(\mathbb{F}_{13})=\{5, 8\}$

The interesting property here is that ${-1}$ is considered a square in ${\mathbb{C}}$, ${\mathbb{F}_5}$ and ${\mathbb{F}_{13}}$, but not in the other systems. Also note that when ${-1}$ is a square in ${\mathbb{F}_p}$, then the sum of the two solutions equals ${p}$. This is because the two solutions are ${n}$ and ${p-n}$.

In general, one observes that ${\mathbb{F}_p}$ has solutions to ${x^2+a=0}$ when ${p\equiv 1\pmod 4}$ and no solutions when ${p\equiv 3\pmod 4}$.

Returning to the equation ${x^2-a=0}$, recall it has no solutions, one solution ${0}$ (when ${a}$ is a multiple of ${p}$, or two solutions ${\pm a}$. The Legendre Symbol codifies this situation over ${\mathbb{F}_p}$:

$\displaystyle \left (\frac{a}{p}\right ) = \begin{cases} -1 \ \ \text{no solutions}\\ \ \ 0\ \ \text{one solution}\\ \ \ 1\ \ \text{two solutions} \end{cases}$

where this convention provides the following niceties (for integer ${k}$):

$\displaystyle \left (\frac{0}{p}\right ) = 0, \ \ \ \left (\frac{1}{p}\right ) = 1, \ \ \ \left (\frac{a}{p}\right ) \left (\frac{b}{p}\right ) = \left (\frac{ab}{p}\right ), \ \ \ \left (\frac{a}{p}\right ) = \left (\frac{a+kp}{p}\right )$
.

Returning to the equation ${x^2+1=0}$, the solution result can be restated:

$\displaystyle \left (\frac{-1}{p}\right ) = \begin{cases}\ \ 1\ \ p\equiv 1\pmod 4\\ \ \ 0\ \ \text{not possible because} \ p\not| \ a\\ -1\ \ p\equiv 3\pmod 4 \end{cases}$

Similarly,

$\displaystyle \left (\frac{2}{p}\right ) = \begin{cases}\ \ 1\ \ p\equiv 1\pmod 8\\ -1\ \ p\equiv 3\pmod 8\\ -1\ \ p\equiv 5\pmod 8\\ \ \ 1\ \ p\equiv 7\pmod 8 \end{cases} \left (\frac{3}{p}\right ) = \begin{cases}\ \ 1\ \ p\equiv 1\pmod {12}\\ -1\ \ p\equiv 5\pmod {12}\\ -1\ \ p\equiv 7\pmod {12}\\ \ \ 1\ \ p\equiv 11\pmod {12} \end{cases}$

$\displaystyle \left (\frac{5}{p}\right ) = \begin{cases}\ \ 1\ \ p\equiv 1\pmod {20}\\ -1\ \ p\equiv 3\pmod {20}\\ -1\ \ p\equiv 7\pmod {20}\\ \ \ 1\ \ p\equiv 9\pmod {20}\\ \ \ 1\ \ p\equiv 11\pmod {20}\\ -1\ \ p\equiv 13\pmod {20}\\ -1\ \ p\equiv 17\pmod {20}\\ \ \ 1\ \ p\equiv 19\pmod {20} \end{cases} \left (\frac{7}{p}\right ) = \begin{cases}\ \ 1\ \ p\equiv 1\pmod {28}\\ \ \ 1\ \ p\equiv 3\pmod {28}\\ -1\ \ p\equiv 5\pmod {28}\\ \ \ 1\ \ p\equiv 9\pmod {28}\\ -1\ \ p\equiv 11\pmod {28}\\ -1\ \ p\equiv 13\pmod {28}\\ -1\ \ p\equiv 15\pmod {28}\\ -1\ \ p\equiv 17\pmod {28}\\ \ \ 1\ \ p\equiv 19\pmod {28}\\ -1\ \ p\equiv 23\pmod {28}\\ \ \ 1\ \ p\equiv 25\pmod {28}\\ \ \ 1\ \ p\equiv 27\pmod {28} \end{cases}$

Studying the patterns above and additional examples, two facts emerge that are surprisingly difficult to prove, but are very useful for subsequent proofs. Let ${a}$ be a positive integer.

If ${p}$ and ${q}$ are odd primes and ${p\equiv q\pmod {4a}}$, then

$\displaystyle \left (\frac{a}{p}\right ) = \left (\frac{a}{q}\right )$

If ${p}$ and ${q}$ are odd primes and ${p+q\equiv 0\pmod {4a}}$, then

$\displaystyle \left (\frac{a}{p}\right ) = \left (\frac{a}{q}\right )$

This brings us to the Quadratic Reciprocity Theorem.

Given ${p}$ and ${q}$ odd primes:

$\displaystyle \left (\frac{-1}{p}\right ) = \begin{cases}\ \ 1\ \ p\equiv 1\pmod 4\\ -1\ \ p\equiv 3\pmod 4 \end{cases} \left (\frac{2}{p}\right ) = \begin{cases}\ \ 1\ \ p\equiv 1\ \rm{ or }\ 7\pmod 8\\ -1\ \ p\equiv 3\ \rm{ or }\ 5\pmod 8 \end{cases}$

If ${p\equiv q \equiv 3\pmod 4 }$ then

$\displaystyle \left (\frac{p}{q}\right ) = -\left (\frac{q}{p}\right )$

If ${p}$ and/or ${q \equiv 1\pmod 4 }$ then

$\displaystyle \left (\frac{p}{q}\right ) = \left (\frac{q}{p}\right )$

### 8. Galois Theory

Motivation

The absolute Galois group of ${\mathbb{Q}}$, call it ${G}$, is a group of symmetries with deep structure, most of it as yet unknown. This structure is being probed, using representations of ${G}$ by standard objects, namely permutation and matrix groups. ${G}$‘s first applications here will be for studying the structure of solution sets of ${\mathbb{Z}}$-equations, and of torsion points of elliptic curves. But ultimately, it is ${G}$‘s shadowy powers themselves that are attracting the attention of number theorists.

${G}$ consists of permutations ${g}$ on ${\overline{\mathbb{Q}}}$ that preserve the four arithmetic operations, and specifically:

$\displaystyle g(a+b)=g(a)+g(b)\rm,\ g(ab)=g(a)g(b)$

Subtraction and division follow from these properties. It is not hard to show that ${G}$ forms a group.

Exactly two elements of ${G}$ are known explicitly in their entirety: the identity permutation ${g_e : g_e(a)=a}$, and the complex conjugation permutation ${g_c: g_c(a+bi)=a-bi}$. But a few partial characterizations of elements of ${G}$ have been discovered.

Magic 1: For ${g \in G}$

$\displaystyle a \in \mathbb{Q} \implies g(a)=a$

Magic 2: For $\displaystyle f(x)=0$ a ${\mathbb{Z}}$-equation

$\displaystyle f(a)=0 \implies f(g(a))=0 \ \ \ [f(g(a))=g(f(a)]$

Magic 2.1: For ${x^2-2=0}$ (an example),

$\displaystyle g(\sqrt 2)= \begin{cases} -\sqrt 2\ \text{for half of}\ g \in G\\ \sqrt 2\ \text{for half of}\ g \in G \end{cases}$

.

The elements of ${G}$ thus permute the roots of each ${\mathbb{Z}}$-polynomial ${p(x)}$. Depending on ${p(x)}$, there are various degrees of freedom that elements of ${G}$ have for permuting the roots.

Magic 3: The existence proof for an element ${g \in G}$ involves selecting all ${p(x)}$ and determining the compatible root permutations (by application of Zorn’s Lemma).

### 9. Elliptic Curves

Motivation

An elliptic curve is a variety ${E}$ for a type of ${\mathbb{Z}}$-equation. For each number field ${A}$, ${E(A)}$ forms an Abelian group. Because of their group structure, more can be understood about elliptic curves than about varieties with unknown structure. Galois groups can be used to permute the roots of the ${\mathbb{Z}}$-equation to further assist study.

The name elliptic curve relates to using ${E}$ to study the arc-length of certain ellipses. They are called curves because ${E(\mathbb{R})}$ can be plotted and geometrically visualized.

The general ${\mathbb{Z}}$-equation related to ${E}$ is

$\displaystyle y^2=x^3+Ax+B$

where ${A}$ and ${B}$ are integers such that the discriminant ${2(4A^3+27B^2)\ne 0}$. The last condition rules out some number systems from the domain of ${E}$, as seen in the example of equation ${y^2=x^3+1}$. For this equation, the discriminant condition becomes ${6 \ne 0}$ or ${6 \not \equiv 0\pmod p}$, ruling out ${\mathbb{F}_2}$ and ${\mathbb{F}_3}$ from the domain of ${E}$. There are two non-degenerate cases. If the discriminant is ${>0}$, the curve has two components, else the curve has one component.

Note that ${E(\mathbb{Z})}$ is just a set; lack of an inverse prevents it from being a group. To make ${E(A)}$ into a group, ${A}$ must be a field and the solution set in ${A}$ must be augmented by a special identity (neutral) element called the point at infinity, ${\mathcal{O}}$, that is considered in some sense to represent the solution ${x=\infty, y=\infty}$.

Two examples for ${y^2=x^3+1}$:

$\displaystyle E(\mathbb{F}_5)=\{(0,1),(0,4), (2,3),(2,2),(4,0),\mathcal{O}\}$

$\displaystyle E(\mathbb{F}_7)=\{(0,1),(0,6), (1,3),(1,4),(2,3),(2,4),(3.0),(4,3),(4,4),(5,0),(6,0),\mathcal{O}\}$

The group operator has complex operation based on the geometry of the curve. Let ${P}$ and ${Q}$ be points on elliptic curve ${E(A)}$. Then draw a line through ${P}$ and ${Q}$. The line will intersect the curve in just three places, ${P}$, ${Q}$, and a third point ${R}$. Negating the y-coordinate of ${R}$ produces the point ${P+Q}$. This and similar geometric constructions allow ${P+Q}$ to be computed for all possible cases:

If ${P=\mathcal{O}}$, then ${P+Q=Q}$.

If ${Q=\mathcal{O}}$, then ${P+Q=P}$.

If ${x_P=x_Q}$ and ${y_P+y_Q=0}$, then ${P+Q=\mathcal{O}}$.

If ${x_P\neq x_Q}$, compute ${\lambda= (y_Q-y_P)/(x_Q-x_P)}$. If ${x_P=x_Q, y_P=y_Q\ne 0}$, compute ${\lambda=(3x_P^2+A)/2y_P}$. Let ${V=y_P-\lambda x_P}$, and compute ${x_{P+Q}=\lambda^2-x_P-x_Q}$, ${y_{P+Q}=-(\lambda x_{P+Q}+v)}$, where ${P+Q=(x_{P+Q},y_{P+Q})}$.

That there is a group lurking in this geometry is amazing and non-trivial to prove, or even to verify in the case of associativity. Inverses are simple enough; the inverse of solution ${(x,y)}$ is ${(x,-y)}$.

The equation for the elliptic curve arises naturally in a 2500 year old problem, called the congruent number problem: find all right triangles with rational sides and integer areas. Letting the area = 1, by some algebra this can be shown to be equivalent to finding ${E(\mathbb{Q})}$ where ${E}$ corresponds to ${y^2=u^3-u}$. In this geometry, the point at infinity ${\mathcal{O}}$ is given geometric perspective as a degenerate solution of a triangle with one side of length ${0}$, the other side of length ${\infty}$, and area = ${1}$.

Define an element ${P}$ of ${E(\mathbb{C})}$ as part of an ${n}$-torsion if

$\displaystyle \stackrel{n \ \rm{times}}{\overbrace{P+P+P+{ \ldots}+P}}=\mathcal{O}$

The above can be abbreviated as ${nP=\mathcal{O}}$. The set of all ${n}$-torsion points is written ${E[n]}$ and is a subgroup of ${E(A)}$. The number of elements in ${E(\overline{\mathbb{Q}})}$ that are ${n}$-torsion is ${n^2}$. The ${n}$-torsion elements of a variety operate in the same manner as the ${n}$-torsion elements of a general group, so that ${nP=\mathcal{O}}$ is analagous to ${g^n=\rm{E}_{\rm{G}}}$, where ${g}$ is an element of a group G and ${\rm{E}_{\rm{G}}}$ is the identity element in group G.

Proceed to Matrices (Also Basic Notions Of Vector Spaces)