Number theory: Part I

Table of contents:

• Introduction: the general strategy of finding homomorphic spaces
• Integral points on hyperplanes: prerequisites
• Integral points on hyperplanes: Bezout, Euclid's algorithm, Gaussian elimination and Smith normal form

---

Introduction

Number theory is just algebra done over the integers. This seems kind of weird at first -- the integer lattice seems like a rather arbitrary lattice to care about; I mean, if you're looking for solutions for an equation over the reals, you can always show existence and approximate the solution by analytic means, but whether or not an arbitrary real number is an integer is just so arbitrary, why would you even CARE about that--

But the integers do have some special structure. The most obvious interesting thing about the integers is divisibility. One can show something isn't a solution by taking both sides $\mod b$ for some $b$ -- i.e. one can get restrictions on the space of possible solutions by considering the problem in $\mathbb{Z} \mod b$. 

This is an example of a much more general strategy in mathematics to restrict the space of possible solutions -- apply a homomorphism to both sides and eliminate non-solutions in the homomorphic space. If you apply an isomorphism, you can also do the converse -- i.e. accept solutions in the isomorphic space.

So we're interested in the structure of $\mathbb{Z}$, so as to know what it can homomorph to. Addition and multiplication are rather important to the structure of $\mathbb{Z}$ -- we like to call this a ring. In fact, $\mathbb{Z}$ is the "free ring". If you know any category theory, this means $\mathbb{Z}$ is the ring that has homomorphisms to every other ring. 

Actually, $\mathbb{Z}$ is the "free ring with no generators" -- the free ring with some generators $X_1,\dots X_n$ is called the polynomial ring with these variables, and is the free object in the category of "rings that contain the elements $X_1,\dots X_n$". BTW this is why Galois theory is so important, because it studies quotients of $K[X]$, the free ring with one generator. Also $\mathbb{Q}$ is the free field, and the rational functions form the free fields with some generators. 

In basic number theory, there are two sorts of such rings to which we will be interested in homomorphisms to: $\mathbb{Z}/b\mathbb{Z}$ (which we've discussed) and $\mathbb{Z}[\alpha]$ for some non-integer $\alpha$. 

This is why the algebraic properties of these rings are of so much importance in number theory -- that's why algebra is so important in number theory. The Chinese remainder theorem -- the statement that the obvious projection map $\mathbb{Z}/(n_1\dots n_k)\mathbb{Z}\to\mathbb{Z}/n_1\mathbb{Z}\times\dots\times\mathbb{Z}/n_k\mathbb{Z}$ is a ring isomorphism -- is such an algebraic property. Stuff about quadratic and higher residues (squares mod $b$) are such algebraic properties. Stuff about when $\mathbb{Z}[\alpha]$ is a UFD, PID blabla are such algebraic properties. We will make reference to them throughout this course without getting into the details of things.

So the topic is solving equations over the integers. In particular, solving polynomial equations over the integers. 

---

Integral points on hyperplanes: prerequisites

The following animation is a picture illustration of Euclid's algorithm:

Make sure you understand exactly what this algorithm is doing at each step, and how it corresponds to Euclid's algorithm as you know it (think of it with a particular example). Why does this work -- how do we know we will finish up the rectangle in a finite number of steps (i.e. actually get a GCD), what property of the integers ensures this?

Anyone got intuition for Bezout's identity? I can say that I'm not a fan of using Euclid's algorithm -- instead, I prefer the following argument: let $d$ be the smallest positive $ax+by$ -- certainly the gcd must divide $d$, but also $d$ must divide $x$ (and analogously $y$), or its remainder will be smaller than $d$. So $d$ must be the gcd.

---

Integral points on hyperplanes: Bezout, Euclid's algorithm, Gaussian elimination and Smith normal form

$$381x+66y=b$$

So Bezout's identity tells us that the equation $a_1x+a_2y=b$ (by convention $a_1, a_2, b$ are known/"constants" while $x, y, z$ are to be solved for/"variables") is solvable iff $\mathrm{gcd}(a_1,a_2)$ divides $b$. In fact it says the equation $\sum a_ix_i=b$ is solvable iff $\mathrm{gcd}((a_i))$ divides $b$. 

In fact it tells us there is an algorithm to compute this solution $x_i$ -- namely, Euclid's algorithm. 

To help us generalize this: the nicest way to think of Euclid's algorithm algorithmically is as a sequence of matrix multiplications. E.g.

$$\begin{align}381&=5\times 66+51\\ 66&=1\times 51+15\\ 51&=3\times 15+6\\15&=2\times 6+3\\6&=2\times 3+0\end{align}$$

$$\begin{align}\left[\begin{array}{c}381\\66\end{array}\right]&=\left[\begin{array}{cc}5&1\\1&0\end{array}\right]\left[\begin{array}{cc}1&1\\1&0\end{array}\right]\left[\begin{array}{cc}3&1\\1&0\end{array}\right]\left[\begin{array}{cc}2&1\\1&0\end{array}\right]\left[\begin{array}{cc}2&1\\1&0\end{array}\right]\left[\begin{array}{c}3\\0\end{array}\right]\\&=\left[\begin{array}{cc}127&52\\22&9\end{array}\right]\left[\begin{array}{c}3\\0\end{array}\right]\\ \left[\begin{array}{cc}3&0\end{array}\right] &= \left[\begin{array}{cc}381&66\end{array}\right]\left[\begin{array}{cc}-9&22\\52&-127\end{array}\right] \end{align}$$

So in effect, we're solving the linear equation (where $\mathbf{a},\mathbf{d}$ are row vectors) $\mathbf{a}\mathbf{x}=b$ by instead solving $\mathbf{d}\mathbf{y}=b$ where $\mathbf{d}=\mathbf{a}\mathbf{T}$ is of the form $(d,0)$ and $\mathbf{T}\in\mathrm{GL}(\mathbb{Z}^2)$. 

Note also that left- (resp. right-) multiplication by $\left[\begin{array}{cc}\lambda&1\\1&0\end{array}\right]$ can also be understood as "add $\lambda$ copies of Row 1 to Row (resp. Col) 2, then switch Row (resp. Col) 1 and Row (resp. Col) 2"  -- i.e.

$$\left[\begin{array}{cc}\lambda&1\\1&0\end{array}\right]=\left[\begin{array}{cc}0&1\\1&0\end{array}\right]\left[\begin{array}{cc}1&0\\\lambda&1\end{array}\right]$$

The group $\mathrm{GL}(\mathbb{Z}^2)$ can be understood as the group of GCD-preserving transformations. (The algorithm to simplify $\mathrm{gcd}(ax+by,cx+dy)$ -- using the identity $\mathrm{gcd}(x+\lambda y, y)=\mathrm{gcd}(x,y)$ -- is precisely Euclid's algorithm.)

But the nice thing about this matrix approach is that it can be used to solve systems of linear equations. It is not sufficient to solve these equations independently and state the conditions as $d_1\mid c_1,\dots d_m\mid c_m$, because the solution sets for each equation needn't intersect (think: $3x+6y=3, 3x+9y=3$). 

Instead, we solve $\mathbf{A}\mathbf{x}=\mathbf{b}$ by solving $\mathbf{D}\mathbf{y}=\mathbf{c}$ where $\mathbf{D}=\mathbf{S}\mathbf{A}\mathbf{T}$, $\mathbf{c}=\mathbf{S}\mathbf{b}$ and $\mathbf{D}$ is diagonal, $\mathbf{S},\mathbf{T}\in\mathrm{GL}(\mathbb{Z}^n)$. This $\mathbf{D}$ is called the Smith normal form of $\mathbf{A}$, and can be seen as a generalization of the Greatest Common Divisor to a set of integer vectors.

If anyone has a good thorough exposition for the algorithm to calculate the Smith normal form -- and some analogous intuition to that for its special case the Euclidean algorithm -- let me know.