\documentclass{article}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}

\newcommand{\OR}{\vee}
\newcommand{\AND}{\wedge}

\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\R}{\mathbb R}
\newcommand{\Q}{\mathbb Q}
\newcommand{\C}{\mathbb C}

\newcommand{\lagrange}[2]{\left( \frac{#1}{#2} \right)}

\newtheorem{thm}{Theorem}[section]
\newtheorem{corollary}[thm]{Corollary}
%%\newtheorem{exercise}[thm]{Exercise}
\newtheorem{lemma}[thm]{Lemma}

\theoremstyle{definition}

\newtheorem{defn}[thm]{Definition}
\newtheorem{example}[thm]{Example}

\DeclareMathOperator{\lcm}{lcm}

\renewcommand{\labelenumi}{\roman{enumi}}

\begin{document}

\title{B10 lecture course : Elementary Number Theory}

\author{Lectures given by Dr Heath-Brown \\ Notes taken by Tom Womack, extra material supplied by\\ Paul
Rowe, Duncan Archer and Rob Hladky \\ }

\date{October 1996}
\maketitle
\tableofcontents
\pagebreak

%%lecture 1

\section{Introduction}

I would like to thank Dr Heath-Brown for giving me permission to publish
this set of notes. The copyright in the content is his; the errors in the
content are mine.

This course is about properties of $\N$, $\Z$ and $\Q$; until you get to
a much higher level, no analysis pokes its ugly head anywhere near this
subject. 

\section{Properties of $\Z$}

$\Z$ has a Euclidean algorithm - that is, $\forall a,b \in \Z$, there is
a $d$ with $d|a$, $d|b$, $s|a, s|b \implies s|d$. Moreover, $\exists
\alpha, \beta \in \Z$ with $\alpha a + \beta b = d$. 

\begin{corollary}
Let $p$ be prime. Then $p|ab \implies p|a$ or $p|b$.
\end{corollary}

\begin{proof}

Suppose $p \not | a$. Then $\exists d = (p,a)$, with $d|p$ so $p=dd'$.
But $p$ is prime, so $d=1$ or $d=p$. If $d=p$ then $d|a$ by definition
of $d$, but $p \not | a$, so $d=1$. 

So $\exists x,y : px+ay=1$. So $b=pbx+aby$. But $p|ab$, so $ab=pc$. So
$b=p(bx+cy)$, so $p|b$. 

\end{proof}

\begin{thm}[Fundamental Theorem of Algebra]

Every $n \in \N$ can be written as a product of increasing prime numbers
in exactly one way. 

\end{thm}

There are two parts to this theorem; that every $n$ can be written in
this way, and that the expression is unique. 

For the first part, let $n$ be the smallest number which can't be
written in that way. Then $n$ is composite (since primes are already
written in that way), $n=pq$ with $n > p,q >1$. But $p$ and $q$ are
$<n$, so can be written as products of primes; concatentate the
expressions. 

For the second part, assume that $n$ is the smallest integer with two or
more representations : $$n = p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k} =
q_1^{e_1} \ldots q_s^{r_s}.$$

If $p_1 = q_1$ then $n/p_1 = n/q_1$ - but $n/p_1$ factorises uniquely. So
$p_1 \not = q_1$. WLOG $p_1 < q_1$.

Now, $p_1 | n \implies p_1 | q_1^{r_1} \ldots q_s^{r_s}$. Apply the corollary
repeatedly until we have $p_1 | q_i$. But $q_i$ is prime, and, by ordering,
$q_i \ge q_1 > p_1$. Contradiction.

\begin{corollary}

Let $a,b$ be coprime positive integers. Then $ab$ is a square iff $a$ and $b$
are both squares.

\end{corollary}

\begin{proof}
Let $ab=c^2$, and $p_1 \ldots p_n$ be all the primes which divide any of $a$, $b$
or $c$. Write $a = \prod p_i^{e_i}$, $b = \prod p_i^{f_i}$, $c=\prod p_i^{g_i}$
with $e_i$, $f_i$, $g_i \ge 0$.

Now $e_i + f_i = 2g_i$ by definition of multiplication. But, since $a$ and $b$
are coprime, $e_i$ and $f_i$ are never both non-zero. So $e_i=2g_i$ or $f_i=2g_i$,
so $a$ and $b$ are both squares.
\end{proof}

This concept doesn't hold universally; for example, over $\Z [ \exp(2i\pi / 23) ]$,
$ab=c^{23}$ doesn't mean both $a$ and $b$ are $23$-rd powers.

\subsection{Prime Numbers}

It's very easy to make long lists of prime numbers, using the Sieve of Eratosthenes
for example (erase multiples of $2$ which are $\ge 4$, multiples of $3$ which are
$\ge 9 \ldots$).

\begin{thm}
\label{infprimes}
There are infinitely many primes
\end{thm}

\begin{proof}

Assume there are only finitely many primes. Multiply them together and add 1 to get
$\lambda$. If $\lambda$ is prime, it's a prime not on the list; if it's composite,
it's divisible by a prime not on the list.
\end{proof}

\begin{thm}
\label{infcomp}
There are sequences of $n$ consecutive composites for every $n$
\end{thm}

\begin{proof}
$N!+2 \ldots N!+N$, for $N=n+1$.
\end{proof}

A corollary of \ref{infprimes} is that $p_{n+1} \le \prod_{i=1}^n p_i +
1$. It's a lousy estimate, though. 

At this point, one of the major features of number theory appears; there
are an awful lot of unsolved problems about, and a vast number of
statements which are easy to make and horrific to prove. For example, we
don't know if there are infinitely many primes of the form $n!+1$, or
infinitely many of any prime constellation (for example the twin
primes). The answers should be `yes' and `yes', but no-one has the
proof. 

There are earlier sequences of consecutive composites for $n$; Marek
Wolf conjectured in a recent paper that the first set of $n$ composite
numbers appears around $\sqrt n \exp(\sqrt n)$. 

We define $\pi(x)$ as the number of prime numbers $\le x$. For example,
$\pi(10^3)=168$, $\pi(10^4)=1229$, $\pi(10^6)=78498$,
$\pi(10^8)=5761455$. 

$\pi(x)/x$ is decreasing, but only slowly (roughly as $1/\log x$). 

\subsection{Estimating $\pi(x)$}

\begin{thm}[the Prime Number Theorem] \label{pnt}$\frac{\pi(x) \log
x}{x} \rightarrow 1$ as $x \rightarrow \infty$ \end{thm}

\begin{defn} If $f(x), g(x) > 0 \forall x$, and $\frac {f(x)} {g(x)}
\rightarrow 1$ as $x \rightarrow \infty$, we write $f(x) \sim g(x)$.
\end{defn}

So the Prime Number Theorem can be written as $\pi(x) \sim \frac {\log
x}x$.  There is a better approximation obtained by $\pi(x) \approx
\int_2^x \frac 1{\log t} {\rm d}t$; unfortunately, $\frac 1{\log t}$
can't be integrated using normal functions. 

Whilst $\pi(x) > \frac{x}{\log x}$ always, $\pi(x)<{\rm Li}(x)$ for
small $x$.  This is with `small' meaning '$<10^{18}$'; Littlewood proved
that $\pi(x) > {\rm Li}(x)$ for infinitely many $x$, and Skewes showed
that the smallest such $x$ was less than $10^{10^{10^{34}}}$.
Fortunately, modern results suggest that $x<10^{1700}$. It's unlikely
that $x$ will ever be found, since it's unlikely that $x<10^{500}$. 

The Prime Number Theorem was first proved in 1896; there is still no
easy proof, though there's one in Hardy and Wright which is merely
fiddly rather than actively incomprehensible. 

\subsection{Corollaries of PNT}

\begin{thm} $p_n \sim n \log n$ \end{thm}

\begin{proof}
Recall that $\pi(p_n)=n$. By theorem \ref{pnt}, $n \sim \frac{p_n}{\log p_n}$, so
$n \log p_n \sim p_n$.

We want to show, therefore, that $\log p_n \sim \log n$. We know that $p_n \ge n$,
so the fraction is always $\ge 1$.

However, $$n \log p_n \sim p_n \implies \frac{n \log p_n}{p_n} \ge 1/2$$ for large enough $n$.
If $\epsilon$ is given, $\log x \le x^\epsilon$ for large enough $x$, so $\log p_n
\le {p_n}^\epsilon$ for $n$ large enough.

So $\frac {n p_n^\epsilon}{p_n} \ge 1/2$ for $n$ big enough, so $p_n^{1-\epsilon}
\le 2n$, and $(1-\epsilon)\log p_n < \log 2n$.

So $$\frac {\log p_n}{\log n} \le \frac{1}{1-\epsilon} \frac{\log 2n}{\log n},$$
and this tends to $1$ as $n \rightarrow \infty$, $\epsilon \rightarrow 0$.
\end{proof}

\begin{corollary}
$p_n < n^2$ for $n$ big enough, since $p_n \le 2n \log n$ and $2n \log n \le n^2$
\end{corollary}

It's not known whether there is always at least one prime between $n^2$ and $(n+1)^2$,
though it seems likely. There is always at least one prime between consecutive cubes, though.

You can model the sequence of primes well by assuming that primes near $x$ occur
following a Poisson process with parameter $(\log x)^{-1}$.

\section{Congruences}

We write $a \equiv b \pmod n$ iff $n | (b-a)$. This is an equivalence
relation for fixed $n$. You can add, multiply and subtract congruences,
but you can't always divide them ($2 \equiv 8 \pmod 6$, but $1 \not
\equiv 4 \pmod 6$). 

This is just another way of writing arithmetic in $\Z / n\Z$; it means
you can work with smaller numbers, so you can check that $2^{30} \equiv
(2^5)^6 \equiv (-1)^6 \equiv 1 \pmod {31}$ without ever having to know that
$2^{30}=1073741824$.

%% this is lecture 3 (actually a mix of lectures 3 and 4; the course goes with
%% different timings in different years)

\subsection{Linear Congruences}

You might want to know when you can solve a linear equation like $ax \equiv b
\pmod m$.

Start off by noticing that, if $d|a$ and $d|m$, $d | ax-b$ (since $ax-b = km$),
so $d|b$. So a necessary condition is that $(a,m)|b$.

If this holds, set $d=(a,m)$, so the equation becomes $dAx \equiv dB \pmod {dM}$;
we can now divide through by $d$, since it's not coprime to the modulus, to get
$Ax \equiv B \pmod M$, with $(A,M)=1$.

We can go further, in fact; if we can solve $Ax \equiv 1 \pmod M$, we have
$AxB \equiv B \pmod M$. So what we need is

\begin{thm}
\label{inverses}
If $(a,m)=1$ then the congruence $ax \equiv 1 \pmod m$ always has a solution, and
it is unique modulo $m$.
\end{thm}

\begin{proof}

$(a,m)=1$, so, using the Euclidean algorithm, we can find $y,z$ with
$ay+zm=1$.  So $m | zm = 1-ay$, so $ay \equiv 1 \pmod m$. 

For uniqueness, suppose that $ax \equiv ax' \equiv 1 \pmod m$. Then $ax \equiv ax'$,
so $m|a(x-x')$. But $(a,m)=1$, so $m|(x-x')$, so $x \equiv x' \pmod m$.
\end{proof}

So we can solve single linear equations. An obvious next question is how
far we can get solving multiple linear equations; simultaneous equations
to the same modulus are fairly straightforward using the standard
elimination methods, but it would be nice to be able to handle several equations
to different moduli.

\subsection{Simultaneous congruences}

\begin{thm}[Chinese Remainder Theorem]

If $m_1, \dots, m_k$ are coprime in pairs, the simultaneous congruences
$x \equiv b_1 \pmod {m_1}, \ldots, x \equiv b_k \pmod {m_k}$ have a unique
solution mod $M = \prod_{i=1}^k m_i$. 

\end{thm}

Note that there need not be a solution if the $m_i$ aren't coprime in pairs; $x \equiv
1 \pmod 4$, $x \equiv 3 \pmod 8$ is clearly impossible.

\begin{proof}

We need to prove existence and uniqueness.

\begin{enumerate}
\item[Existence]
Let $M = m_i n_i$ (eg $n_3 = m_1 m_2 m_4 \ldots m_k$). Then $(m_i,n_i)=1$, since the
$m_i$ are coprime in pairs, so, by theorem \ref{inverses}, we can solve $n_i x_i
\equiv 1 \pmod {m_i}$ for each $i$.

Now, let $$x = x_1 n_1 b_1 + \ldots + x_k n_k b_k.$$

Working modulo each $m_i$ in turn, we have $m_i | n_j$ for $j \not = i$, so the
only term left is $x_i n_i b_i = b_i$ by definition of the $x_i$. So $x$
satisfies the simultaneous congruences.

\item[Uniqueness] Suppose $x' \equiv b_i \pmod {m_i}$ for all $i$. Then
$x' \equiv x \pmod {m_i} \forall i$ since both $\equiv b_i$. So $m_i |
x'-x$. But the $m_i$ are pairwise coprime, so $\prod m_i | x'-x$, so $x'
\equiv x \pmod M$. 

\end{enumerate}
\end{proof}

\begin{example}

We solve $10x \equiv 2 \pmod {26}$, $7x \equiv 3 \pmod {20}$.

$(26,20) \not = 1$, but $(10,2,26)=2$, so we can convert the first
equation to $5x \equiv 1 \pmod {13}$. 

To apply the Chinese Remainder Theorem, we must start off by reducing
the equations to the form $x \equiv b_i \pmod {m_i}$. So we solve
$5b_1-1=13y$ getting $b_1=8$, and we solve $7b_2-3=20y$, getting
$b_2=9$. 

Now, we see that $m_i = n_{3-i}$ (that is, there are only two factors so
the cofactor in each case is the other one). 

So we solve $20x_1 \equiv 1 \pmod {13}$, getting $x_1=2$, and $13x_2
\equiv 1 \pmod {20}$, getting $x_2 = 17$. And, by the Chinese Remainder
Theorem, we have $x \equiv n_1 x_1 b_1 + n_2 x_2 b_2 \equiv 20 \cdot 2
\cdot 8 + 13 \cdot 17 \cdot 9 \equiv 2309 \equiv 229 \pmod {260}$.

\end{example}

\section{Arithmetic Functions}

\subsection{Arithmetic Functions}

\begin{defn}
An {\em arithmetic function} is a function from $\N$ to $\C$ (often from
$\N$ to $\N$).
\end{defn}

Examples of arithmetic functions include obvious ones like the polynomials,
and also some less usual ones :

$d(n)$, the divisor function, which is $|\{k \in \N : k|n\}|$.

$\sigma(n) = \sum_{k|n}k$

$\omega(n)$, the number of prime factors of $n$

$\phi(n)$, the Euler function, which is $|\{k \in \N : k<n, (k,n)=1\}|$.

\subsection{Multiplicative functions}

\begin{defn}
We say that an arithmetic function is {\em multiplicative} if $f(mn) = f(m)
f(n)$ whenever $m,n \in \N$ and $(m,n)=1$.
\end{defn}

For example, $d$ is multiplicative, whilst $\omega$ isn't (since $\omega(2)=1,
\omega(3)=1, \omega(6) = 2 \not = 1$.

%% this is lecture four


\begin{thm}
$\phi$ is a multiplicative function
\end{thm}

\begin{proof}
$\phi$ is the number of invertible elements in $\Z / n\Z$.

Let $a$ run over a complete set of invertible elements mod $m$, and $b$
do the same mod $n$. So there are $\phi(m) a$'s, and $\phi(n) b$'s. We
want to show that, if $(m,n)=1$, $am+bn$ runs over a complete set of
invertible elements mod $mn$. This would imply $\phi(mn)=\phi(m)\phi(n)$.

So we need to show that

\begin{enumerate}

\item $am+bn \equiv a'm+b'n \implies a=a'$, $b=b'$. Working mod $m$ gives
$bn \equiv b'n$, so $b=b'$ since $(n,m)=1$; repeating the argument backwards
gives $a=a'$.

\item $(an+bm, nm)=1$. $(an+bm,m) = (an,m) = 1$ since $a$ and $n$ are each
coprime to $m$. Similarly, $(an+bm,n)=(bm,n)=1$. So $(an+bm, nm)=1$.

\item If $c$ is invertible mod $mn$, $\exists a,b : c \equiv am+bn \pmod
{mn}$.  But $mx \equiv c \mod n$ is solvable since $(m,n)=1$; let $b$ be a
solution.  If $d>1$ divides both $b$ and $n$, $d|c$, so $(c,n)>1$, so
$(c,mn) \not = 1$.  So $(b,n)=1$. Similarly to get $(a,m)=1$. Now $am+bn
\equiv am \equiv c \pmod n$, and $am+bn \equiv bm \equiv c \pmod n$. So
the numbers are congruent mod $m$ and mod $n$, so mod $mn$.

\end{enumerate}
\end{proof}

\begin{corollary}
$$\phi(n) = n \prod_{p|n}(1-1/p).$$
\end{corollary}

\begin{proof}

$\phi(p^e)$ is the number of integers $< p^e$ without a factor $p$, so is
$p^e (1-1/p)$. The result follows by multiplicativity.
\end{proof}

\subsection{Making multiplicative functions}

\begin{thm}
If $f$ is multiplicative, then $g(n) = \sum_{d|n} f(d)$ is multiplicative.
\end{thm}

\begin{proof}
$g(mn) = \sum_{d|mn} f(d)$. If $u$ and $v$ run over the divisors of $m$ and $n$
respectivly, then $d=uv$ runs over the divisors of $mn$, if $(m,n)=1$ :

If $uv=u'v'$, then $u|u'v'$. But $u|m$, $v'|n \implies (u,v')=1$, so $u|u'$.
Similarly, $u'|u$, so $u=u'$, $v=v'$, so all the $uv$ are different.

$uv|mn$ trivially (since $(m,n)=1$).

If $\alpha | mn$, set $u=(\alpha,m)$ and $v=\alpha / u$. Then $\alpha = uv$,
and $\alpha | mn \implies \frac \alpha u | \frac {mn}u$. But $d/u$ and $m/u$
are coprime, so $\alpha/u$ divides $n$. So $v|n$, $u|m$.
\end{proof}

This produces a number of new multiplicative functions :

$f(x)=1$ gives the divisor-counting function $d$, so that's
multiplicative. $f(x)=x$ gives the sum of the divisors, so $\sigma$ is
multiplicative. 

Any multiplicative function can be given a direct form in terms of the prime
factorisation of the argument : $$d(p_1^{e_1} \ldots) = (e_1+1)(e_2+1) \ldots,$$
$$\sigma(p_1^{e_1} \ldots) = \prod \frac {p_i^{e_i+1}-1}{p_i-1}.$$

\subsection{Perfect Numbers}

\begin{defn}
$n \in \N$ is {\em perfect} iff $\sigma(n)=2n$. If $\sigma(n)<2n$, $n$ is called
{\em deficient}; if $\sigma(n)>2n$, $n$ is called {\em abundant}.
\end{defn}

That is, the sum of the proper divisors of a perfect number is the
number itself.  Some perfect numbers are $6$, $28$, $496$, $33550336$
and $2^{60} \cdot (2^{61}-1)$. 

It is an open question whether there are infinitely many perfect numbers
(though the answer is clearly `yes'), and whether there are any odd ones
(where the answer is less clear); these are probably the oldset
well-defined unanswered questions. 

Euclid proved that, if $p=2^n-1$ is prime, then $p \cdot (p+1)/2$ is
perfect; such primes are called Mersenne primes, and it's an open
question as to whether there are infinitely many of them. 36 are
currently known, the largest being $2^{2976221}-1$. 

%%lecture 5

\begin{thm}
If $n=ab$ with $a,b \ge 2$ then $2^n-1$ is composite
\end{thm}

\begin{proof}
$2^n-1 = x^b-1$ for $x=2^a$; $x^b-1$ factors algebraically as $(x-1)
(x^{b-1}+x^{b-2} \ldots +1)$.
\end{proof}

\begin{thm}
If $q | 2^p-1$ with $p,q$ prime, then $q \equiv 1 \pmod {2p}$.
\end{thm}

\begin{proof}
Consider the group of order $q-1$ of the non-zero residues mod $q$. By
Lagrange's theorem, $2^{q-1} \equiv 1 \pmod q$. Now, $2^p \equiv 1
\pmod q$, since $q|2^p-1$.

Now, if $p \not | q-1$, $(p,q-1)=1$ so $\exists x,y : px+(q-1)y=1$. But
then $2^{px} 2^{q-1}y \equiv 2^1 \equiv 1^x 1^y = 1$, which is a
contradiction. So $p | q-1$, so $q \equiv 1 \pmod p$. 

$q \equiv 1 \pmod {2p}$ since $q$ is prime, hence odd.
\end{proof}

\begin{thm}[Euler]
Every even perfect number is of the form $2^{p-1} (2^p-1)$.
\end{thm}

\begin{proof}

An even $n$ is of the form $2^e b$ with $e \ge 1$ and $b$ odd. Now, $\sigma(n)
= \sigma(2^e) \sigma(b)$ since $\sigma$ is multiplicative and $(2^e,b)=1$ since
one has only factors of 2 and the other is odd.

So $\sigma(n) = \sigma(b) 2^{e+1}-1$. So, for $n$ to be perfect, we require

$$2^{e+1}b = (2^{e+1}-1) \sigma(b).$$

So $2^{e+1} | \sigma(b)$, so $\sigma(b) = 2^{e+1}k$, which means $b=(2^{e+1}-1)k$.
If $k>1$ then, since $1$, $k$ and $b$ are all divisors of $b$, $\sigma(b)
\ge 1+b+k > k+b = 2^{e+1}k = \sigma(b)$. Oops.

So $k=1$, $b=2^{e+1}-1$, and $\sigma(b)=2^{e+1}$ - so $b$ must be prime.
\end{proof}

So any even perfect number is of Euclid's form. No-one's ever seen an odd perfect
number, but you can prove results about them anyway :

\begin{thm}
Any odd perfect number has at least three prime factors
\end{thm}

\begin{proof}

Suppose $n = p_1^{e_1} p_2^{e_2}$, where $p_2$ might be 1. Then 

$$\sigma(n) = \prod \left( \frac {p_i^{e_i+1}-1}{p_i-1} \right)
< \prod \frac{p_i^{e_i+1}}{p_i+1} = \prod p_i^{e_i} \prod \frac {p_i}{p_i-1}
= n \prod \frac {p_i}{p_i-1}.$$

So $2 = \prod_{i=1}^k p_i (p_i-1)^{-1}$.

Write $P_i$ for the $i$th odd prime number. Assume $P_i$ are written in
ascending order, so $p_i \ge P_i$. So $2 < \prod_{i=1}^k
\frac{p_i}{p_i-1}$.  But this is impossible if $k=1$ or $k=2$, since the
product is too small. Increasing $k$ might produce good results after a
bit of searching. 
\end{proof}

In fact, it's known that any odd perfect number has at least eight prime
factors. 

\subsection{The M\"obius Function}

We define $\mu(1)=1$, and 
$$\mu(p_1^{e_1} \ldots p_k^{e_k}) = 
\begin{cases}
(-1)^k & e_i=1 \forall i \\
0&\exists i : e_i \ge 2
\end{cases}
$$

The function is multiplicative by definition, and equal to zero at any power or
number divisible by a power.

\begin{thm}
\label{indicator_fn}
$\sum_{d|n} \mu(d) = 0$ unless $n=1$, whereupon it equals $1$.
\end{thm}

\begin{proof}
$\mu(d)$ is multiplicative, so $f(n) = \sum_{d|n} \mu(d)$ is multiplicative.
But $f(p^k) = \mu(1) + \mu(p) + \mu(p^2) \ldots = 1 - 1 + 0 + 0 \ldots$.

So $f$ is 1 iff $n=1$.
\end{proof}

This function is important because of the following

\begin{thm}[The M\"obius Inversion Theorem]
If $G(n) = \sum_{d|n} F(d)$, then $$F(n) = \sum_{d|n} \mu(d) G(\frac nd) =
\sum_{d|n} G(d) \mu(\frac nd).$$
\end{thm}

\begin{proof}
\begin{align*}
\sum_{d|n} \mu(d) G(\frac nd) &= \sum_{d|n} \mu(d) \sum_{c|\frac nd} f(c) \\
&= \sum_{cd|n} \mu(d) f(c) \\
&= \sum_{c|n} f(c) \sum_{d|\frac nc}\mu(d) = f(n)
\end{align*}
\end{proof}

\begin{thm}
\label{mobiusconverse}
If $f(n) = \sum_{d|n} \mu(d) g(\frac nd)$, then $g(n) = \sum_{d|n} f(d)$.
\end{thm}

\begin{proof}
\begin{align*}
\sum_{d|n} f(d) &= \sum_{d|n} f(\frac nd)\\
&= \sum_{d|n} \sum{c|\frac nd} \mu(\frac n{cd}) g(c) \\
&= \sum_{cd|n} \mu(\frac n{cd}) g(c) \\
&= \sum_{c|n} g(c) \sum_{d|\frac nc}\mu(\frac n{cd}) = g(n)
\end{align*}
\end{proof}

%%lecture 6

\begin{thm}
$\sum_{d|n} \phi(d) = n$.
\end{thm}

We will present three different proofs of this

\begin{proof}[Using multiplicativity]

 $\phi$ is multiplicative, so $f(n) = \sum_{d|n} \phi(d)$ is also
multiplicative. And

$$f(p^e) = \phi(1) + \phi(p) + \ldots + \phi(p^e) = 1 + (p-1) + p(p-1) +
\ldots + p^{e-1}(p-1) = p^e.$$

So $f(n)=n \forall n$.
\end{proof}

\begin{proof}[Using the inclusion-exclusion principle]

Let $m=p_1^{e_1} \ldots p_k^{e_k}$. Then

\begin{align*}
\phi(m) &= m \cdot 1-\frac 1{p_1} \cdot 1-\frac 1{p_2} \ldots \\
&= m - \left[ \sum_{i\le k}\frac m{p_i} \right]
+ \left[ \sum_{i<j\le k} \frac m{p_ip_j} \right]
+ \ldots + (-1)^k \frac{m}{p_1p_2\ldots p_k} \\
&= \sum_{d|m} \frac md \mu(d) \\
&= \sum_{d|m} d\mu(\frac md) \\
\end{align*}

So, by theorem \ref{mobiusconverse}, $m = \sum_{d|m} \phi(d)$.

\end{proof}

\begin{proof}[Counting by $(m,n)$]

$$n = |\{ m \in \N : m \le n \}|.$$ We'll group the $m$'s according to the
value of $(m,n)$, giving

$$n=\sum_{d|n}  |\{ m \in N : m \le n, (m,n)=d \}|.$$ 

Now, if $m \le n$ and $(m,n)=d$, we have $m=rd$ and $n=sd$ with
$(r,s)=1$. So $$n = \sum_{d|n} |\{ r \in N : r \le d, (r,d)=1 \}| =
\sum_{d|n} \phi(d)$$

\end{proof}

This is quite a useful result, because it tells you that $\phi$ is in some
sense the inverse of $n$.

\begin{thm}
$$\sum_{d|n} d(\frac nd) \phi(d) = \sigma(n)$$
\end{thm}

\begin{proof}
Note that $d(k) = \sum_{d|k} 1 = \sum_{uv=k} 1$.

So we have 

\begin{align*}
\sum_{d|n} d(\frac nd) \phi(d) = \sum_{d|n} \phi(d) \sum_{uv = \frac nd} 1
&= \sum_{duv=n} \phi(d) \\
&= \sum_{v|n} \sum_{d|\frac nv} \phi(d) = \sum_{v|n} \frac nv = \sigma(n).
\end{align*}
\end{proof}

\section{Congruences to prime moduli}

For $p$ prime, $\Z / p\Z$ is not merely a ring but a field. It has $p$
elements, and the non-zero ones for a group of order $p-1$ under
multiplication. Applying Lagrange's Theorem gives $n^{p-1} \equiv 1
\pmod p$ if $p \not | n$, which is called Fermat's Little Theorem or
FLT. 

In general, if $n$ is composite, the residues coprime to $n$ will form a
group of order $\phi(n)$ under multiplication, so $a^{\phi(n)} \equiv 1
\pmod n$ whenever $(a,n)=1$. This is called Euler's Theorem.

\subsection{The multiplicative group of $\Z_p$ is cyclic}

\begin{lemma}
If $a^u \equiv 1 \pmod n$, $a^v \equiv 1 \pmod n$ and $(a,n)=1$ then
$a^{(u,v)} \equiv 1 \pmod n$
\end{lemma}

\begin{proof}
$a^u \equiv 1$ means that the order of $a$ has a factor $u$; $a^v \equiv 1$
means that it has a factor $v$, so it has a factor $(u,v)$.
\end{proof}

\begin{lemma}
\label{orders}
If $e | p-1$, then there are exactly $e$ solutions to $x^e-1 \equiv 0 \pmod p$.
\end{lemma}

Note that this only works for prime $p$; $x^2-1 \equiv 0 \pmod 8$ has four roots.

\begin{proof}
A polynomial of degree $d$ has at most $d$ roots over any field, so we need to
prove the polynomial has at least $d$ roots.

$$p-1 = ef \implies x^{p-1}-1 = (x^e-1)(x^{ef-e} + x^{ef-2e} + \ldots + x^e + 1).$$

But $x^{p-1}=1$ by Fermat's little theorem. But the first factor has at most $e$
roots, and the second at most $e(f-1)$ roots. But $e+e(f-1) = p-1$, so both factors
must have their full complements of roots. In particular, $x^e-1$ has $e$ roots.
\end{proof}

\begin{thm}
If $e | p-1$ then there are precisely $\phi(e)$ elements of order $e$ in the
multiplicative group mod $p$.
\end{thm}

Again, this only works for prime $p$; there are no elements of order 4 in
the multiplicative group modulo 8.

\begin{proof}

We work inductively. For $e=1$, there is $1$ element of order $1$. 

$x^e \equiv 1 \pmod p \iff |x| | e$. There are exactly $e$ elements with
order dividing $e$, by lemma \ref{orders}; let $f(d)$ be the number of
order-$d$ elements, so $\sum_{d|e} f(d) = e$. 

Now $f(d) = \phi(d)$ for all $d<e$, by the inductive step, so $\sum_{d|e} f(d)
= \sum_{d|e} \phi(d) = e$. Comparing terms in the series gives $f(e)=\phi(e)$.
\end{proof}

As a corollary to this result, we have that the multiplicative group of $\Z_p$ is
cyclic with $\phi(p-1)$ generators, which we call the {\em primitive roots} of
$\Z_p$.

\subsection{A very bad primality test}

\begin{thm}
$x^{p-1} - 1 \equiv (x-1)(x-2) \ldots (x-(p-1)) \pmod p$
\end{thm}

\begin{proof}
Both sides are polynomials of degree $p-1$ with the same roots, so must be equal to
within a constant term, and comparing the coefficient of $x^{p-1}$ gives the constant
term equal to 1.
\end{proof}

Putting $x=0$ in the above gives (since $p$ is odd)

\begin{thm}[Wilson's Theorem]
$$-1 \equiv (-1)^{p-1} (p-1)! \equiv (p-1)! \pmod p$$
\end{thm}

This in fact gives a (totally useless) test for primality :

$$d|n \implies d|(n-1)! \implies (n-1)! \not \equiv -1 \pmod n,$$

so $(p-1)! \equiv -1 \pmod p$ iff $p$ is prime.

\begin{thm}

Let $s$ be the sum of the primitive roots mod $p$. Then $s \equiv
\mu(p-1) \pmod p$. 

\end{thm}

\begin{proof}

Let $g$ be a primitive root. Then the $\phi(p-1)$ primitive roots will
be $g^n$, where $n \in [1, p-1]$ with $(n,p-1)=1$. 

Define $f(n)$ to be 1 iff $(n,p-1)=1$. Then $s = \sum_{n=1}^{p-1}
f(n)g^n$. 

But we can also write $f(n)$ as $\sum_{d | (n,p-1)} \mu(d)$, by theorem
\ref{indicator_fn}. So

$$s = \sum_{n=1}^{p-1} g^n \sum_{d | (n,p-1)} \mu(d) = \sum_{d | p-1} \mu(d)
\sum_{d|n, n \in [1,p-1]} g^n.$$

Write $s(d) =\sum_{d|n} g^n$, so $s = \sum_{d|p-1} \mu(d) s(d)$.

If $d=p-1$, $s(d) = g^{p-1} \equiv 1 \pmod p$. If $d < p-1$, we have

$$s(d) \equiv \sum_{m=1}^{\frac{p-1}d} g^{md} = \frac{(g^d)^{\frac{p-1}d + 1}
- g^d} {g^d-1}$$

by the formula for the sum of a geometric progression. But $g^{p+1-d}-g^d
= g^d-g^d \equiv 0 \pmod p$, and $g^d-1 \not \equiv 0$. So $p | s(d)$ since
it divides the numerator and not the denominator, and $s(d)$ is an integer.

So $s(d) \equiv 0$ for $d<p-1$, so $s \equiv \mu(p-1) g^{p-1} = \mu(p-1)$.

\end{proof}

%% about lecture 7

\subsection{The multiplicative group of $\Z / p^n\Z$ is cyclic for $p \ge 3$}

We extend the definition of `primitive root' such that a primitive root
of $p^n$ is a generator of the multiplicative group mod $p^n$. 

\begin{thm}
The multiplicative group (mod $p^n$) is cyclic if $p \ge 3$. In fact, there is
a $g$ which is a primitive root for $p^r \forall r$.
\end{thm}

\begin{proof}
The proof proceeds in three steps :

\begin{enumerate}

\item $\exists g$, a primitive root mod $p$, such that $g^{p-1} \not = 1
\pmod {p^2}$. 

Let $g_1$ be any primitive root mod $p$. Unless $g_1^{p-1} \equiv 1
\pmod {p^2}$, we can take $g=g_1$. 

If $g_1^{p-1} \equiv 1 \pmod {p^2}$, consider $g = g_1+p$. This is still a
primitive root mod $p$, and

\begin{align*}
g^{p-1} &= g_1^{p-1} + \binom{p-1}1 g_1^{p-2}p + \binom{p-1}2 g_2^{p-3}p^2 \ldots \\
&\equiv 1 + (p-1) g_1^{p-2} p \pmod {p^2} \\
&\not \equiv 1 \pmod {p^2}
\end{align*}

since $p^2$ does not divide $p(p-1)g_1^{p-2}$.

\item For such a $g$, $g^{(p-1)p^r} \not \equiv 1 \pmod {p^{r+2}}$ for $r \ge 0$

For this bit, we work by induction on $r$. $r=0$ is given by the
previous part. 

$g^{(p-1)p^r} = g^{\phi(p^{r+1})} \equiv 1 \pmod {p^{r+1}}$, by Euler's theorem, so $g^{(p-1)p^r}
= 1 + lp^{r+1}$. By induction, we have that the left-hand side $\not \equiv 1 \pmod {p^{r+2}}$,
so $p \not | l$. So

\begin{align*}
g^{(p-1)p^{r+1}} &= (g^{(p-1)p^r})^p = (1+p^{r+1}l)^p \\
                 &= 1 + p^{r+1}l\binom p1 + \ldots \\
                 &\equiv 1 + p^{r+2}l \pmod {p^{r+3}}
\end{align*}

since $p^{r+3} | (p^{r+1}l)^k \binom pk$ for $k \ge 2$.

\item Such a $g$ is a primitive root mod $p^t$ for all $t \ge 1$.

Let the order of $g$ mod $p^t$ be $m$. Then $g^m \equiv 1 \pmod {p^t}$, so
in particular $g^m \equiv 1 \pmod p$, so $g$ is a primitive root mod
$p$ and $p-1 | m$.

Also, $g^{\phi(p^t)} \equiv 1 \pmod {p^t}$, so $m | (p-1)p^{t-1}$. Write
$m = (p-1)k$, where $k | p^{t-1}$.

Then either $k = p^{t-1}$, in which case $m = (p-1)p^{t-1} = \phi(p^t)$
and $g$ is a primitive root of $p^t$, or $k | p^{t-2}$, whereupon $m |
(p-1)p^{t-2}$, so $g^{(p-1)p^{t-2}} \equiv 1 \pmod {p^t}$, which
contradicts part ii. 

\end{enumerate}
\end{proof}

\subsection{Non-linear congruences}

\begin{thm}[Chevalley, 1936]
\label{chevalley}
Let $f(x_1, \dots, x_n)$ be an integer polynomial of total degree $d$. Then, if $n>d$, the
number of solutions of $f(x_1, \dots, x_n) \equiv 0 \pmod p$ is a multiple of $p$.
\end{thm}

\begin{corollary}
If $f$ has zero constant term and $n>d$, there is a solution other than $x_i \equiv 0$. For example,
a quadratic form in more than two variables has a non-trivial zero $\pmod p$.
\end{corollary}

To prove this theorem, we start with the following
\begin{lemma}
$\sum_{x=0}^{p-1} x^n \equiv 0 \pmod p$ for $0 \le n < p-1$.
\end{lemma}

\begin{proof}
If $n=0$ then the sum is equal to $p$, so $\equiv 0 \pmod p$.

Otherwise, the non-one $x_i$ are equivalent to $g^{r_i}$ in some order,
where $g$ is a primitive root.  So $$\sum_{i=1}^{p-1} x^n =
\sum_{i=1}^{p-1} g^{nr_i} = \sum_{i=1}^{p-1} g^ni = \frac
{g^{np}-g^n}{g^n-1}.$$

The numerator is $g^n((g^n)^{p-1}-1)$, which is $\equiv 0 \pmod p$; the
denominator is not divisible by $p$ since $n < p-1$, so the fraction
(which is an integer) is divisible by $p$ so $\equiv 0 \pmod p$. 

\end{proof}

\begin{proof}[Proof of \ref{chevalley}]

$1-f(x_1,\ldots,x_m) ^ {p-1} \equiv 1$ if $f \equiv 0 \pmod p$, and 0
otherwise. So the number of solutions to the equation is $$\sum_{x_1,
\ldots,x_n} [1-f(x_1, \dots, x_n)^{p-1}] \pmod p.$$ 

Now, expand $f^{p-1}$ to get terms of the form $c x_1^{e_1} \ldots
x_n^{e_n}$, of total degree $\le d(p-1)$, which is $< n(p-1)$. So some
exponent must have $e_{i_0} < p-1$. 

The contribution from this term is $$c \sum_{x_1=0}^{p-1}
\sum_{x_2=0}^{p-1} \ldots \sum_{x_n=0}^{p-1} x_1^{e_1} \ldots x_n^{e_n}
= c \sum_{x_1=0}^{p-1} x_1^{e_1} \ldots \sum_{x_n=0}^{p-1} x_n^{e_n}.$$ 

By the lemma, the $i_0$th factor is zero modulo $p$, so that term
contributes 0 modulo $p$, so the whole sum is 0 modulo $p$. 

\end{proof}

\section{Quadratic Residues}

\subsection{Solving Quadratic Equations}

When can we solve $x^2 \equiv n \pmod p$?

It's clearly not always possible; the only remainders given by a square
modulo $7$ are $0,1,2,4$. 

\begin{defn}

Let $p$ be an odd prime. If $p \not | n$ and $x^2 \equiv n \pmod p$ is
solvable, we say that $n$ is a {\em quadratic residue} of $p$. If $p
\not | n$ and the congruence is not solvable, we say $n$ is a {\em
quadratic non-residue}. If $p|n$, $n$ is neither.

\end{defn}

We summarise this definition with the {\em Lagrange symbol} :

$$\lagrange np =
\begin{cases}
+1 & \text{residue}\\
-1 & \text{non-residue}\\
0 & p|n
\end{cases}
$$

Note that, if $m \equiv n \pmod p$, $\lagrange mp = \lagrange np$.

\begin{thm}
If $p \ge 3$ then there are $\frac {p-1}2$ residues and $\frac{p-1}2$ non-residues.
So $\sum_{n=1}^p \lagrange np = 0$.
\end{thm}

\begin{proof}

We will show that the mapping $n \rightarrow n^2$ is a bijection between the numbers between
$1$ and $\frac {p-1}2$ and the quadratic residues.

\begin{enumerate}

\item[1-to-1]
If $n^2 \equiv m^2 \pmod p$, $p | m^2-n^2 = (m-n)(m+n)$. $m+n < p$, so we have $p | m-n$ and
$m \equiv n \pmod p$.

\item[onto]
If $r$ is a quadratic residue then $s^2 \equiv r \pmod p$ for some $s$. $s \not = 0$ since $0$
is not relevant in this context; if $s \le \frac{p-1}2$ then we send $s$ to $r$, if not we send
$p-s$ to $r$.

\end{enumerate}
\end{proof}

%% lecture 8 

\subsection{Ways of finding $\lagrange np$}

\begin{thm}[Euler's Criterion]
$\lagrange np \equiv n^{(p-1)/2} \pmod p$
\end{thm}

\begin{proof}

If $p|n$, then the left- and right-hand sides are equal. 

If $n \equiv x^2 \pmod p$, then $p \not | x$ and $n^{(p-1)/2} = x^{p-1}
\equiv 1 = \lagrange np$. 

Now, $x^{(p-1)/2} \equiv 1$ has at most $\frac {p-1}2$ roots; we have
found exactly that many, namely the quadratic residues, so there can be
no more. And, letting $m = x^{(p-1)/2}$, we have $m^2 = x^{p-1} \equiv 1
\pmod p$, for which we know two roots $\pm 1$. So $m \equiv \pm 1 \pmod
p$ -- and we know $m \not \equiv +1$, so $m \equiv -1 = \lagrange np$. 

\end{proof}

\begin{corollary}
$$\lagrange ap \lagrange bp = \lagrange{ab}p.$$
\end{corollary}

So the product of two residues or two non-residues is a residue; the
product of a non-residue and a residue is a residue. 

\begin{corollary}
$$\lagrange{-1}p = (-1)^{(p-1)/2} = \begin{cases}
+1 & p \equiv 1 \pmod 4 \\
-1 & p \equiv -1 \pmod 4
\end{cases}
$$

So $x^2+1 \equiv 0 \pmod p$ is solvable if $p \equiv 1 \pmod 4$, not if
$p \equiv -1 \pmod 4$.
\end{corollary}

\begin{defn}
The {\em least positive residue} of $m \pmod p$ is the unique $n \in \N$
with $m \equiv n \pmod p$ and $m<p$.
\end{defn}

\begin{defn}
If $x \in \R$, define $[x] = \max \{n \in \N : n \le x\}$.
\end{defn}

Then the least positive residue of $m$ is $m-p[\frac mp]$.

\begin{thm}[Gauss' Lemma]

If $p \not | n$, then $\lagrange np = (-1)^\nu$, where $\nu$ is the number of integers
in $[1,\frac{p-1}2]$ for which the least positive residue of $mn$ exceeds $\frac p2$.

\end{thm}

For example, consider $\lagrange {4}{11}$. We take $m=1,2,3,4,5$, $mn=4,8,12,16,20$,
$mn \equiv 4,8,1,5,9$, so $\nu=2$ and $\lagrange{4}{11} = 1$.

\begin{proof}

Consider the numbers $mn$, reduced to lie between $- \frac p2$ and
$\frac p2$ (by subtracting $p$ from the numbers $> \frac p2$ in the
list). This produces a list of remainders $r_1, \dots, r_\mu, s_1,
\ldots, s_\nu$, where $0 \le r_i,s_j < \frac p2$ and $\mu + \nu =
\frac{p-1}2$. 

If any of the $r_i$ or $s_j$ are zero, then $p | mn$, which is
impossible since $p \not | m$, $p \not| n$. So $1 \le r_i,s_j \le \frac
{p-1}2$. 

We claim that the $r_i$ and $s_j$ are all different. If $r_i=r_j$ or
$s_i=s_j$, then we have $mn \equiv m'n$ for some $m,m'$, so, since $p
\not | n$, $m \equiv m'$. If $r_i = s_j$, then $r_i \equiv mn$, $p-s_j
\equiv m'n$, so $mn+m'n \equiv r_i + p - s_j \equiv 0 \pmod p$, so $p |
(m+m')n$, which is impossible since $p \not | n$ and $m+m' < p$. So
$r_i, s_j$ are a rearrangement of $1 \ldots \frac{p-1}2$. 

Now,

$$\prod_{m=1}^{\frac{p-1}2} mn = n^\frac{p-1}2 \prod_{m=1}^{\frac{p-1}2}
m = n^\frac{p-1}2 \frac{p-1}2 ! \equiv \lagrange np \frac{p-1}2 !$$

And $$\prod_{m=1}^{\frac{p-1}2} mn \equiv \prod_{i=1}^\mu r_i
\prod_{j=1}^\nu (p-s_j) \equiv \prod_{i=1}^\mu r_i \prod_{j=1}^\nu -s_j
= \frac{p-1}2! (-1)^\nu.$$

So $\lagrange np = (-1)^\nu$.

\end{proof}

\begin{corollary}

2 is a quadratic residue iff $p \equiv \pm 1 \pmod 8$. Putting $p=8n+r$,
we have $(p^2-1)/8 = 8n^2 + 2nr + \frac{r^2-1}{8}$, so $(-1)^{\frac {p^2-1}8}
= 1$ if $p \equiv \pm1 \pmod 8$ and $=-1$ otherwise. 

\end{corollary}

\begin{proof}

Take $n=2$ in Gauss' Lemma. So we consider the numbers $2, 4, \ldots, p-1$,
all of which are equal to their least positive residues, and we want to know how
many of them are $>p/2$. $\nu = \frac{p-1}2 - |\{2r \le \frac p2\}|$; $2r
\le \frac p2 \iff r \le \frac p4$, so $\nu = \frac{p-1}2 - [\frac p4]$.

Now run through the possible residues modulo 8.

\end{proof}

\subsection{Quadratic Reciprocity}

\begin{thm}[The Law of Quadratic Reciprocity]
\label{quadrec}
If $p,q$ are primes $\ge 3$, then $\lagrange pq=\lagrange qp$ unless $p \equiv q \equiv 3 \pmod 4$,
in which case $\lagrange pq = -\lagrange qp$. Equivalently, $$\lagrange pq = \lagrange qp \cdot (-1)^{(\frac
{p-1}2)(\frac{q-1}2)}.$$
\end{thm}

\begin{example}

\begin{align*}
\lagrange{1222}{907} &= \lagrange{315}{907} \\
&= \lagrange{3}{907}^2 \lagrange{5}{907} \lagrange{7}{907} \\
&= 1 \cdot \lagrange{907}{5} \cdot -\lagrange{907}{7} \\
&= \lagrange 25 \cdot -\lagrange 47 \\
&= \lagrange 25 \cdot - (\lagrange 27 \cdot \lagrange 27) \\
&= \lagrange 25 \cdot -1 \\
&= +1
\end{align*}

since $5 \not \equiv \pm1 \pmod 8$.

\end{example}

%% lecture 9

\begin{lemma}
Let $p,q$ be distinct odd primes, $p = 2p'+1$, $q=2q'+1$.

Write $S(q,p)=\sum_{n=1}^{p'} [\frac{nq}p]$ and $S(p,q) = \sum_{m=1}^{q'} [\frac{mp}q]$.

Then $S(p,q) + S(q,p) = p'q'$.
\end{lemma}

\begin{proof}
Note that $[x] = \sum_{m \le x} 1$ for $x\ge 0$.

$$S(q,p) = \sum_{n \le p'} \sum{m \le \frac{nq}p} 1.$$

Now, $m \le \frac{nq}p \le \frac{p'q}p < \frac{pq}{2p} = \frac q2$, so
$m \le q'$.  So $S(q,p)$ is counting the pairs $(n,m)$ with $n \le p'$,
$m \le q'$, and $mp \le nq$. Similarly, $S(p,q)$ is counting the pairs
$(n,m)$ with $n \le p'$, $m \le q'$, and $mq \le np$. 

So $S(p,q)+S(q,p)$ is counting all the pairs; and none of them are counted twice, since
$mp=nq \implies p|n$, which is impossible since $n\le p' <p$. So $S(p,q)+S(q,p) = p'q'$.
\end{proof}


\subsection{Proof of Quadratic Reciprocity}

We apply Gauss' Lemma to $\lagrange qp$. Consider $nq$ for $1<n\le p'$;
these can be written $nq = p \lfloor \frac{nq}p \rfloor + u_n$ for $1
\le u_n < p$, and Gauss' Lemma gives us $\lagrange qp = (-1)^\nu$, where
$\nu$ of the $u_n$ are $> p/2$. 

We use the notation from the proof of the lemma : $u_n = r_i$ ($\mu$
times), and $u_n = p-s_i$ ($\nu$ times). 

Now, $$\sum_{n=1}^{p'} u_n = \sum r_i + \sum (p-s_i);$$ working mod 2, this
is $\sum r_i + \nu + \sum s_j$. Recalling that the $r_i$ and $s_j$
together cover the whole of $1 \dots p'$, we have $\sum u_n \equiv \nu +
\sum_{i=1}^{p'} i \equiv \nu + \frac{p'(1+p')}2 \pmod 2$. 

On the other hand,

$$\sum_{i=1}^{p'} nq = q \sum_{i=1}^{p'} i = \sum_{i=1}^{p'} p
[\frac{nq}p] + u_n = pS(q,p) + \sum_1^{p'} u_n \equiv S(q,p) + \sum_{i=1}^{p'}
i + \nu.$$

So $(q-1) \sum_{i=1}^{p'}i \equiv S(q,p)+\nu$. $q$ is odd, so
$S(q,p)+\nu$ is even, so $S(q,p)$ and $\nu$ are of the same parity, so
$\lagrange qp = (-1)^{S(q,p)}$. 

So $$\lagrange qp \lagrange pq = (-1)^{S(q,p)S(p,q)} = (-1)^{p'q'}$$

which is the Quadratic Reciprocity Theorem

\section{Writing numbers as sums of squares}

$1 = 1^2$, $2=1^2+1^2$, $3=1^2+1^2+1^2$, $4=2^2$, $5=2^2+1^2, 6=2^2+1^2+1^2,
7=2^2+1^2+1^2+1^2, 8=2^2+2^2 \ldots$.

It appears that four squares are enough, and there are clearly numbers which
can't be written as a sum of less than four squares.

Now, considering norms in $\C$ is probably the easiest way to establish that
$$(x^2+y^2)(z^2+t^2) = (xz-yt)^2 + (xt+yz)^2.$$

So, if $a$ and $b$ can be written as a sum of two squares, so can $ab$. Clearly
the sum of two squares is equal to $0, 1$ or $2 \pmod 4$, so $a \equiv 3 \pmod 4$
is out of the question.

\subsection{Two squares}

\begin{thm}
\label{sumoftwosquares}
Suppose $n \in \N$ and $n | N^2+1$. Then $\exists a,b \in \N$ with $a \equiv
Nb \pmod n$ and $n=a^2+b^2$.
\end{thm}

We will need quite a bit of mechanics to prove this result, so observe first that
it implies

\begin{corollary}[Fermat, 1670]
If $p$ is prime, $p \equiv 1 \pmod 4$, then $p$ can be written as a sum of two
squares
\end{corollary}

\begin{proof}
If $p \equiv 1 \pmod 4$, then $\left( \frac {-1}p \right) = +1$, so there is an
$N$ with $N^2 \equiv -1 \pmod p$, so theorem \ref{sumoftwosquares} applies.
\end{proof}

To begin the proof, we need the following result:

\begin{thm}[Dirichlet's Approximation Theorem]
\label{dirichlet_approximation}

Let $x \in \R$ and $l \in \N$. Then $\exists u \in \Z$ and $v \in \N$ with $v \le l$
and $|x-\frac uv| \le \frac{1}{v(l+1)}$.
\end{thm}

\begin{proof}

Consider the $l+1$ complex numbers $y_v = \exp(2 \pi ivx)$, where $v \in [0 \dots l]$.
These lie on the unit circle.

Since there are $l+1$ of them, there are two with argument differing by $\le \frac{2\pi}
{l+1}$, by the pigeonhole principle. Call these $y_v$ and $y_{v'}$ with $v>v'$.

So $|2vx\pi - 2v'x\pi - 2u\pi| \le \frac{2\pi}{l+1}$ for some $u \in \Z$. Put $v_2
= v - v'$, a number between $1$ and $l$. So $|2\pi v_2 x - 2 \pi u| \le \frac{2\pi}{l+1}$.

So $$|x-\frac u {v_2}| \le \frac{1}{v_2(l+1)}.$$

\end{proof}

\begin{proof}[Proof of theorem \ref{sumoftwosquares}]

Take $x=\frac Nn$, $l = \lfloor \sqrt n \rfloor$.

So $\exists b,c \in \Z$, with $0<b\le l$ and $| \frac Nn - \frac cb| \le \frac 1 {b(l+1)}$.

But $\sqrt n < l+1$, so $\frac Nn - \frac cb < \frac 1 {b \sqrt n}$.

Now set $a = Nb-nc$; $a \equiv Nb \pmod n$, and 
$$a^2+b^2 \equiv N^2b^2+b^2 \equiv b^2(N^2+1) \equiv 0 \pmod n.$$

But $a$ and $b$ are quite small;

$$\frac Nn - \frac cb = \frac {Nb-nc}{nb} = \frac {a}{nb} < \frac{1}{b \sqrt n}.$$

so $|a| < \sqrt n$, and $|b| < \sqrt n$ by definition. So $a^2+b^2<2n$, and is a
multiple of $n$, and is $>0$. So $a^2+b^2=n$.

\end{proof}

\begin{thm}
If $p \equiv 1 \pmod 4$ is a sum of two squares, the representation $p=a^2+b^2$ is
essentially unique
\end{thm}

\begin{proof}

Let $p=a^2+b^2 = c^2+d^2$. One of $a$ and $b$ is even, the other odd,
and similarly for $c$ and $d$; WLOG, $a,c$ are even and $b,d$ odd, with
$a>c$ and $b<d$. 

So $(a-c,b+d) = 2s$ and $(a+c,d-b)=2t$. Explicitly, $a-c = 2sA, b+d=2sB,
a+c=2tC, d-b=2tD$. 

$a^2-c^2=d^2-b^2$, so $4stAC=4stBD$ and $AC=BD$. $(A,B)=1$ and $(C,D)=1$, so
$A | BD \implies A|D$; similarly, $D|A$, and $A,D>0$. So $A=D$ and $B=C$.

So $2a = 2sA+2tC$, $2b = 2sB-2tD$. So

\begin{align*}
p=a^2+b^2 &= (sA+tC)^2+(sB-tD)^2 = (sA+Bt)^2 + (Bs-At)^2\\
& = (A^2+B^2)(s^2+t^2)
\end{align*}

which is a contradiction, since $p$ is prime and $A,B,s,t > 0$.

\end{proof}

This means that, if you can write $n$ as a sum of two squares in two different ways,
$n$ is composite and can be factored in the following way :

$5141 = 71^2+10^2 = 55^2+46^2$, so $a=46,b=55,c=10,d=71$. So $(a-c,b-d) = (36,126)
= 18 = 2 \cdot 9$, so $s=9$. And $(a+c,d-b) = (56,16) = 8 = 2 \cdot 4$, so $t=4$.
So $s^2+t^2 | 5141$, so $97 | 5141$, and $5141 = 53 \cdot 97$.

\begin{thm}
$n$ is representable as a sum of two squares iff every primes $p \equiv 3 \pmod 4$
in the factorisation of $n$ appears to an even power.
\end{thm}

\begin{proof}

One direction is easy : if

$$n = 2^e p_1^{e_1} p_2^{e_2} \ldots q_1^{2f_1} q_2^{2f_2} \ldots,$$

with $p_i \equiv 1 \pmod 4$ and $q_i \equiv 3 \pmod 4$, then we have

$2=1^2+1^2$, $p_i = a_i^2+b_i^2$, $q_j^2 =q_j^2+0^2$. So $n$ is a product of sums
of two squares, so itself a sum of two squares.

%%lecture 10

For the other way, suppose $a^2+b^2=q^g m$, with $q \not| m$ and $q \equiv 3 \pmod 4$.
Assume $g$ is odd, $g=2f+1$. There are two cases :

\begin{enumerate}

\item If $q^{f+1} | a$, then $q^{2f+1}|a^2$ and so $q^{2f+1}|b^2$. Now, this is an
odd power dividing a square, so in fact $q^{2f+2}|b^2$, and $q^{2f+2}|a^2$. So
$q^{2f+2} | a^2+b^2 = q^{2f+1}m$, so $q|m$, which is a contradiction.

\item If $(q^{f+1},a)=q^g$ for $g \le f$, we have $q^{2g} | q^{2f+1}m$, and
$q^{2g}|a^2$, so $q^{2g}|b^2$ so $q^g|b$.

Put $a = \alpha q^g$, $b = \beta q^g$. Then $\alpha^2+\beta^2 =
q^{2f-2g+1}m$. So $q|{alpha^2+\beta^2}$. But $q \not| \alpha$, so
$\exists \gamma : \alpha\gamma \equiv 1 \pmod q$. So
$\gamma^2(\alpha^2+\beta^2) \equiv 0 \equiv 1 + (\beta\gamma)^2 \pmod
q$. 

But $\left( \frac{-1}q \right) = -1$, since $q \equiv 3 \pmod 4$. So there's a
contradiction there.
\end{enumerate}

So $g$ is even.

\end{proof}

\subsection{Primes of the form $x^2+5y^2$}

Working mod 4 and mod 5, we have $p = x^2 + 5y^2 \implies p \equiv \pm1 \pmod 5$
and $p \equiv 1 \mod 4$, so either $p=5$ or $p \equiv 1,9 \pmod {20}$.

These congruences are necessary, but they are in fact also sufficient :

$p=5$ clearly works. If $p \equiv 1,9 \pmod {20}$, then
$$\lagrange{-5}{p} = \lagrange{-1}p \lagrange 5p = (+1) \lagrange p5 = 1,$$ since
$p \equiv 1$ or $4 \pmod 5$.

So $\exists n : n^2+5 \equiv 0 \pmod p$.

By Dirichlet's Theorem, there exist $c,y$ with $|\frac np-\frac cy| \le \frac 1 {y(1+l}$
and $y \in [1,l]$. Let $x=cy-np$, so $\frac x {py} \le \frac 1{y(l+1)}$. Moreover,
$x^2+5y^2 \equiv (Ny)^2+5y^2 \equiv y^2(n^2+5) \equiv 0 \pmod p$.

So $x^2+5y^2=kp$, and $0<kp\le (\frac p {l+1}) + 5l^2$. Essentially, the right-hand
side has a minimum at $l=\frac {\sqrt p}{\sqrt[4]5}$.

So let $l = \lfloor p^{1/2} 5^{-1/4} \rfloor$, so $l+1 > p^{1/2}5^{-1/4}$.

So $(\frac{p}{l+1})^2 + 5l^2 < \frac {p^2}{p/\sqrt 5}+\frac{5p}{\sqrt 5} = 2p\sqrt 5$,
and so $k$ is between $0$ and $2 \sqrt 5$.

So $k=1,2,3,4$. $k=2$ and $k=3$ are ruled out by considering the equation modulo 5;
if $x^2+5y^2=4p$, then $4 | x^2+5y^2$, so $x$ and $y$ are both even (work modulo 4;
were $x$ and $y$ both odd, $x^2+5y^2 \equiv 2 \pmod 4$. So halve them to get a
solution to $x^2+5y^2=p$.

The problem's not always that easy; there are no necessary and sufficient conditions
using only congruences for $p=x^2 + 14y^2$.

\subsection{Sums of three squares}

There is no nice multiplication identity; $3 \in S_3$, $5 \in S_3$ but $15 \not \in
S_3$.

\begin{thm}[Legendre, 1798]
$n \in \N$ is a sum of three or fewer squares iff $n$ is not of the form $4^k (8l+7)$.
\end{thm}

It's easy to prove that you can't write $n$ of that form as a sum of three squares;
the proof the other direction is too hard for this course, and also for Legendre.

\subsection{Sums of four squares}

\begin{thm}[Lagrange, 1770]
\label{foursquares}
Every positive integer is a sum of $4$ squares
\end{thm}

We start off with a useful lemma due to Euler :

\begin{lemma}
\label{mulfour}
$$(x_1^2+x_2^2+x_3^2+x_4^2) (y_1^2 + y_2^2 + y_3^2 + y_4^2) = (z_1^2 +
z_2^2 + z_3^2 + z_4^2),$$ where

$$z_1 = x_1y_1 + x_2y_2 + x_3y_3 + x_4y_4$$
$$z_2 = x_1y_2 - x_2y_1 - x_3y_4 + x_4y_3$$
$$z_3 = x_1y_3 - x_3y_1 - x_4y_2 + x_2y_4$$
$$z_4 = x_1y_4 - x_4y_1 - x_2y_3 + x_3y_2$$
\end{lemma}

\begin{proof}

As a cop-out, I could suggest evaluating both sides and showing that they're equal.
Alternatively, use the representation of the quaternions as $2 \times 2$ matrices
over $\C$ :

$$
\begin{pmatrix}
\alpha_1 & -\alpha_2 \\ \bar \alpha_2 & \bar \alpha_1
\end{pmatrix}
\begin{pmatrix}
\beta_1 & -\beta_2 \\ \bar {\beta_2} & \bar{\beta_1}
\end{pmatrix}
=
\begin{pmatrix}
\gamma_1 & -\gamma_2 \\ \bar{\gamma_2} & \bar{\gamma_1}
\end{pmatrix}
$$

where $\gamma_1 = \alpha_1 \beta_1 - \alpha_2 \bar{\beta_2}$ and
$\gamma_2 = \bar{\alpha_2}\beta_1 + \bar{\alpha_1 \beta_2}$;
put $\alpha_1 = x_1 + ix_2$, $\alpha_2 = x_3+ix_4$, $\beta_1 = y_1 +
iy_2$, $\beta_2 = y_3+iy_4$, $\gamma_1 = z_1 + iz_2$, $\gamma_2 = z_3 +
iz_4$ with $x_i, y_i, z_i$ as in the statement of the problem, and note
that the determinants of the matrices are respectively $\sum x_i^2$,
$\sum y_i^2$ and $\sum z_i^2$.  \end{proof}

So, to prove Lagrange's theorem, we need to prove it for prime numbers
not equal to 2. 

\begin{lemma}
If $p \ge 3$ is prime, then $\exists x,y$ with $p | 1+x^2+y^2$.
\end{lemma}

\begin{proof}

This is automatic by Chevalley's Theorem. Alternatively, let $x$ run
through the numbers from $0$ to $\frac{p-1}2$. Then $x^2$ are distinct
mod $p$, so $-(x^2+1)$ are also distinct, and there are $\frac{p+1}2$ of
these. 

Similarly, let $y$ run through $0 \ldots \frac{p-1}2$. These all have
distinct squares, and there are $\frac{p+1}2$ of those. But there are
only $p$ residue classes in total, and $p+1$ elements in the union of
the sets. So there's an overlap somewhere. 

So $-1-x^2 \equiv y^2 \pmod p$ has a solution, which is a solution to
$1+x^2+y^2 = 0 \pmod p$ also.  \end{proof}

\begin{proof}[Proof of theorem \ref{foursquares}]

Take $p$ an odd prime, and $x,y$ with $p | 1+x^2+y^2$. $x,y < \frac p2$,
so $x^2+y^2+1 = kp \le \frac{p^2}2 + 1 < p^2$. So $k<p$. 

Let $k_0$ be the least number such that $k_0 p$ is a sum of four
squares. It's defined (since $k$ would work), and in $[1,p]$. 

Now, $k_0$ is odd. For, if $k_0 = 2k_1$, we have $2k_1p =
a^2+b^2+c^2+d^2$. Arrange these with $a \equiv b \pmod 2$ and $c \equiv
d \pmod 2$, and notice that

$$k_1 p = (\frac{a+b}2)^2 + (\frac{a-b}2)^2 + (\frac{c+d}2)^2 +
(\frac{c-d}2)^2$$

with $k_1 < k_0$. But $k_0$ was minimal. So $k_0$ is odd. 

%% lecture 11

So we have $k_0 p = x_1^2 + x_2^2 + x_3^2 + x_4^2$ with $k_0<p$ and odd.
Choose $b_i$ with $x_i = y_i + k_0 b_i$, so $x_i \equiv y_i \pmod
{k_0}$, and $-\frac{k_0}2 < y_i \le \frac{k_0}2$. Since $k_0$ is odd,
$|y_i| < \frac{k_0}2$. If all the $y_i$ are zero, $k_0 | x_i$ for each
$i$, so $k_0^2 | x_i^2$, so $k_0^2 | k_0 p$. So $k_0 | p$, and $k_0=1$. 

If not, at least one of them is non-zero, $\sum y_i^2 > 0$. Also, $\sum
y_i^2 < \sum \frac{k_0^2}4 < k_0^2$. And $x_i \equiv y_i \pmod {k_0}$, so
$\sum y_i^2 \equiv \sum x_i^2 \equiv 0 \pmod {k_0}$. So

$$\sum y_i^2 = k_0 k_1, 0 < k_1 < k_2.$$

Now use lemma \ref{mulfour} to write $\sum x_i^2 \sum y_i^2 = \sum
z_i^2$. It emerges (since $x_i \equiv y_i$), that each of the $z_i
\equiv \sum y_i^2 \pmod {k_0}$, and in fact are zero mod $k_0$. So we can
divide through by $k_0^2$, to get $$pk_1 = \sum_{i=1}^4
(\frac{z_i}{m_0})^2.$$ So $k_0$ isn't minimal. This is a contradiction,
so all the $y_i$ must be zero, so $k_0 = 1$. 

\end{proof}

\section{Irrational numbers and approximations by rationals}

\begin{thm}

Let $f(x) \in \Z(x)$ be a monic polynomial. Then any rational root is an
integer which divides the constant term of $f$. 

\end{thm}

\begin{proof}

$f(x) = x^n + a_{n-1}x^{n-1} + \ldots +a_0$. $f(\frac uv)=0$, with
$(u,v)=1$. We need to show that $v=1$ and $u|a_0$. 

Multiply through by $v^n$ to get $u^n + a_{n-1}u^{n-1}v + \ldots + a_0
v^n = 0$.  $v$ clearly divides all but the first term of this, so $v |
u^n$. But $(u,v)=1$, so $v=1$. 

Similarly, $u | a_0 v^n$, since it divides all the other terms, so
$u|a_0$. 

\end{proof}

So non-trivial algebraic numbers are irrational.

\subsection{Some irrational numbers}

\begin{thm}
$\log_{10}(n)$ is irrational unless $n=10^\alpha$ for $\alpha \in \Z$.
\end{thm}

\begin{proof}
Suppose $\log_{10}(n) = \frac ab$. Then $n = 10^{a/b}$, so $n^b = 10^a$. Now compare
prime factors for a contradiction.
\end{proof}

\begin{thm}[Lambert, 1761]
$e$ is irrational
\end{thm}

\begin{proof}

$e = 2 + \frac{1}{2!} + \frac{1}{3!} + \ldots$; suppose $e=\frac mn$
with $(m,n)=1$. 

If $n \ge 1$, then $$n!e = 2n! + \frac{n!}{2!} + \frac {n!}{3!} + \ldots
+ s + t$$

where $s = \frac{n!}{(n+1)!} + \frac{n!}{(n+2)!} \ldots$ is an integer,
and $t$ is strictly positive and $<1$ by comparison with the geometric
progression $(n+1)^{-1} + (n+1)^{-2} \ldots$. 

So $n!e-s \in \Z$, but also $n!e-s \in (0,1)$. But there are no integers
strictly between 0 and 1, so this is a contradiction \end{proof}

\begin{thm}[Lambert, 1761]
$\pi$ is irrational
\end{thm}

His proof was rather fiddly; what we're giving here is a much later proof of the
irrationality of $\pi^2$.

\begin{proof}[Proof due to Niven, 1947]

Suppose $\pi^2 = \frac ab$, with $(a,b)=1$, and $a, b \in \N$.

We define $$f(x) = \frac{x^n(1-x)^n}{n!} = \frac{1}{n!} \sum_{i=n}^{2n} c_ix^i.$$

So 

$$f^{(m)}(0) = 
\begin{cases}
0 & m<n, m>2n\\
\frac{m!}{n!}c_m \in \Z & m \in [n,2n]
\end{cases}
$$

$f(x) = f(1-x)$, so the same thing happens at $x=1$. Define

$$G(x) = b^n (\pi^{2n}f(x) - \pi^{2n-2} f^{(2)}(x) + \pi^{2n-4} f^{(4)}(x) \ldots).$$

Putting $x=0$, and noting that $b^n \pi^{2k} = b^{n-k} a^k \in \Z$, we have 
$G(0) \in \Z$, $G(1) \in \Z$.

Now, $$\frac{\rm d}{{\rm d}x} ( G' \sin \pi x - \pi G \cos \pi x) = G'' \sin \pi x
+ G' \pi \cos \pi x - G' \pi \cos \pi x + \pi^2 G \sin \pi x.$$

But 

$$G'' + \pi^2 G = b^n \pi^{2n+2} f(x) = \pi^2 a^n f(x)$$

since all the other terms cancel. So

$$\int_0^1 \pi a^n f(x) \sin \pi x = \left[ \frac 1\pi ( G'(x) \sin \pi x - \pi
G \cos \pi x) \right]_0^1 = G(1)+G(0).$$

since $\sin \pi x$ vanishes at the endpoints. This is an integer.

But $f(x) \in (0,\frac 1{n!})$, and $\sin \pi x \in [0,1]$. So the
integral is $\le \frac {\pi a^n}{n!}$, which tends to $0$ as $n
\rightarrow \infty$, and so is $<1$ for $n$ large enough. So it's not an
integer. This is the desired contradiction. 

\end{proof}

\subsection{Approximations by rationals}

$\Q$ is dense in $\R$, so $x \in \R \implies \exists$ a sequence of rationals
tending to $x$. We ask how close you can get with a restricted denominator.

By Dirichlet's theorem, $x \in \R$, $q \in \N \implies \exists a \in \Z, p \in [1,q]
\cap \N$, with $|x-\frac ap| < \frac{1}{p(q+1)} < \frac{1}{p^2}$.

This isn't a very exciting result for rationals, since you could simply take $\frac ap=x$.

If $\frac aq \not = \frac uv$, $|\frac uv-\frac aq| = |\frac {uq-av}{vq}|$. $uq-av
\not= 0 \implies |\frac uv-\frac aq| \ge \frac{1}{vq} \implies q \le v$.

This suggests the following theorem :

\begin{thm}
$x \in \Q$ has only finitely many good rational approximations; $x$ irrational has
infinitely many.
\end{thm}

%%lecture 12 still missing

%%Rob's lecture 12, which fits in my lecture 13 slot

\subsection{Transcendental numbers}

\begin{thm}[Liouville]

Let $\alpha$ be an irrational root of a polynomial over $\Z$ of degree
$n$. Then there is a constant $c$, depending on the polynomial, such
that $$|\alpha - \frac pq| \ge \frac{c(f)}{q^n} \forall p \in \Z,
\forall q \in \N.$$ 

\end{thm}

\begin{defn}

$\alpha \in \C$ is {\em transcendental} iff there is no polynomial over
$\Z$ of which $\alpha$ is a root. 

\end{defn}

\begin{thm}
$x = 10^{-1!} + 10^{-2!} + 10^{-3!} \ldots$ is transcendental.
\end{thm}

\begin{proof}

$x$ is clearly irrational, since its decimal expansion never repeats.
Suppose $f(x)=0$ for some polynomial in $x$ of degree $n$. Then $\exists
c>0 : |\alpha - \frac pq| > \frac{c}{q^n}$.

But, if you take $q=10^{k!}$ and $a = 10^{k!} (10^{-1!} + 10^{-2!} +
\dots + 10^{-k!})$, you find an approximation with 

\begin{align*}|\alpha - \frac qa| &= 10^{-(k+1)!} + 10^{-(k+2)!} \ldots
\\ &< 10^{-(k+1)!} (1 + 10^{-1} + 10^{-2} \ldots) \\&= \frac {10}9
10^{-(k+1)!} = \frac{10}9 q^{-(k+1)} \end{align*}

Taking $k$ large enough makes it impossible for $\alpha$ to be a root of
a polynomial of any degree.

\end{proof}

\begin{thm}[Roth, 1955]
Let $f(x) \in \Z[x]$ be non-constant with an irrational root. Then

$$\exists c(f,\epsilon) : |\alpha - \frac pq| \ge
\frac{c(f,\epsilon)}{q^{2+\epsilon}}.$$ 
\end{thm}

This improves $q^n$ to $q^{2+\epsilon}$ in Liouville's theorem; it is a
best possible result, since there are infinitely many approximations to
(say) $\sqrt 2$ with error $\le \frac{1}{q^2}$. The proof is difficult.


\section{Diophantine equations}

These were studied by Diophantus, around 250AD.

\begin{defn}
A {\em Diophantine equation} is a polynomial equation with integer coefficients,
usually in several variables, to be solved in the integers or over $\Q$.
\end{defn}

Probably the most famous Diophantine equation is Fermat's Last Theorem.
There is no general theory of Diophantine equations; we've already met
two, namely the equations $x^2+y^2=n$ and $x^2+y^2+z^2+t^2=n$. We'll go through
a number of Diophantine equations to find methods that come in useful in general.

\subsection{$x^3+2y^3 = 13$ : Congruences}

We work modulo 9; $x^3 \equiv 0, \pm 1 \pmod 9$, so $x^3 + 2y^3 \equiv
0,1,8, 2,3,1, 6,7,8 \pmod 9$. In particular, $x^3 + 2y^3 \not \equiv 4
\pmod 9$, so the value 13 is impossible. 

\subsection{$x^3 + 2y^3 = 4z^3$ : Least counterexample}

If $z=0$ then either $x=y=0$ or $\frac xy ^3 = -2$, the latter of which is impossible.
So we look for a solution with $z \not= 0$.

Take a solution with minimal value of $|z|$. Then $2 | 4z^3 = x^3 + 2y^3$, so $2|x^3$,
so $2|x$, so $x=2X$.

So $8X^3 + 2y^3 = 4z^3$, so $4X^3 + y^3 = 2z^3$, so $2|y^3$, so $2|y$, so $y=2Y$.

So $4X^3 + 8Y^3 = 2z^3$, so $2X^3 + 4Y^3 = z^3$, so $2 | z^3$, so $2|z$, so $z=2Z$.

So $2X^3 + 4Y^3 = 8Z^3$, so $X^3 + 2Y^3 = 4Z^3$, with $Z = z/2$. But $z$ was supposed
to be minimal and non-zero, so this is impossible.

\subsection{$x^2=y^3+7$: Using quadratic residues}

\begin{thm}
\label{x^2+7}
$x^2 = y^3+7$ has no solutions
\end{thm}

\begin{proof}

If $2|y$ then $8|y^3$, so $x^2 \equiv 7 \pmod 8$, which is impossible.
So $y$ is odd, so $x$ is even. 

If $y \equiv 3 \pmod 4$ then $x^2 = y^3+7 \equiv 2 \pmod 4$ -- which is
also impossible. So $y \equiv 1 \mod 4$. 

But $x^2+1 \equiv y^3+8 = (y+2)(y^2-2y+4)$. $y+2$ is odd, so, letting $p$
be any prime divisor of $y+2$, we have $p | x^2+1$, so $\lagrange{-1}p = +1$,
so $p \equiv 1 \mod 4$.

So $y+2$ is entirely a product of primes of the form $4k+1$, so $y+2 \equiv 1
\pmod 4$ provided that it's positive. But $y \equiv 1 \pmod 4$, so $y+2 < 0$,
so $y < -2$, so $y^3 < -8$, so $y^3+7 < -1$, so can't possibly be a square
\end{proof}

\subsection{$x^2+y^2=z^2$}

\begin{thm}
If $x^2+y^2=z^2$ with $x,y,z \in \N$, then there exist $a,b,c \in N$ such that
either $(x,y,z)$ or $(y,x,z)$ are of the form $(a(b^2-c^2),2abc,a(b^2+c^2))$.
\end{thm}

\begin{proof}

Obviously, anything of that form satisfies $x^2+y^2=z^2$. 

For the converse, let $a=(x,y)$. Then $a^2 | x^2+y^2 = z^2$, so $a|z$.
Put $x=aX, y=aY, z=aZ$. 

So $X^2+Y^2=Z^2$, with $(X,Y)=1$. So $X$ and $Y$ aren't both even, and,
were they both odd, we'd have $Z^2 \equiv 2 \pmod 4$. So, WLOG, $X$ is
odd and $Y$ is even, so $Z$ is odd. 

So $\frac{X+Z}2$ and $\frac{X-Z}2$ are integral and coprime, so $\frac
{Y^2}4 = \frac{X+Z}2 \frac{X-Z}2$. Multiplying through by 4, we have
that $X+Z$ and $X-Z$ have product a square; being coprime, they must
both be squares. Call them $b^2$ and $c^2$ to get the form above. 

\end{proof}

%%lecture 14

\subsection{$x^4 + y^4 = z^4$}

\begin{thm} $x^4 + y^4 = z^2$ has no solutions in $\N$ \end{thm}

The proof of this theorem uses infinite descent, otherwise known as
least-counterexample or backwards induction. 

\begin{proof} Suppose $(x,y)=d>1$. Then $d^4 | x^4+y^4 = z^2$, so $d^2 |
z$. So $$\left( \frac xd \right) ^4 + \left( \frac yd \right)^4 = \left(
\frac z{d^2} \right) ^2.$$ So we may take $(x,y)=1$. 

Then $(x^2)^2 + (y^2)^2 = z^2$. Using the general solution for the
order-2 equation, we have $x^2=b^2-c^2$, $y^2=2bc$, $z^2=b^2+c^2$ with
$b,c$ coprime and of opposite parity. 

If $b$ is even, $c$ is odd, and then $x^2 \equiv 3 \mod 4$. So $b$ is
odd, $c$ is even, and $y^2=2bc$ is even, so $y$ is even. 

Now, $(\frac y2)^2 = \frac{bc}2$. $b$ and $\frac c2$ are coprime, their
product is a square, so they are both squares. $b=B^2$, $\frac c2 =
C^2$. So $\frac y2 = BC$, $x^2 = b^2-c^2$, so $b^2 = x^2+c^2 = x^2 +
4C^4 = B^4$. So $z=B^4 + 4C^4$. 

Now, $(B^2)^2 = (x^2 + (2C)^2)^2$ with $(B^2, 2C^2) = (b,c) = 1$. So $B^2
= u^2 + v^2$, and either $x=u^2-v^2$, $C^2=uv$ or $x=2uv$, $2C^2=u^2-v^2$.

But $2C^2$ is even, so $B^2$ is odd, so $x$ is odd. So $x=u^2-v^2$, $C^2=uv$,
with $u,v$ coprime with opposite parities. So we can put $u=m^2$, $v=n^2$.
So $B^2 = m^4+n^4$ with $B<z$. So we can go on down forever.
\end{proof}

A very similar proof to that one gives that $X^4 + 4Y^4 = Z^4$ has no solutions
in $\N$.

\subsection{Pell's equation}

Pell's equation is $x^2 - Dy^2=1$ with $x,y \in \N$ and a fixed $D \in \N$.

If $D=d^2$, we have $(x-dy)(x+dy)=1$, so $x=1$, $y=0$.

\begin{thm}
Given $D \in \N$ not a square, and $x_0,y_0$ with $x_0^2 - Dy_0^2 = 1$, $y_0$
minimal non-zero, all solutions to Pell's equation are of the form $x+y\sqrt D
= (x_0 + y_0 \sqrt D)^n$.
\end{thm}

\begin{proof}
Define $N : \Z^2 \rightarrow \Z$ as $N(a,b)=a^2-Db^2$ - this is the norm function.
Then $(a+b\sqrt D)(c+d\sqrt D) = e+f\sqrt D \implies e=ac+Dbd, f=bc+ad$.

So $N(a,b)N(c,d)=N(e,f)$.

It's now fairly clear that, for any solution $(x,y)$, $N(x,y) =
N(x_0,y_0)^n = 1$. The hard bit is proving that those are the only solutions.

Let $x,y$ be a solution. Note that $x_0, y_0 \in \N$, so $x_0 + y_0
\sqrt D > 1$.  So $$\exists n>0 : (x_0 + y_0 \sqrt D)^n \le x+y\sqrt D
\le (x_0 + y_0 \sqrt D)^{n+1}.$$

Now, consider $(x+y\sqrt D)(x_0-y_0 \sqrt D)^n = a+b \sqrt D$ for some
$a,b \in \Z$. $N(a,b)=1$, so $a^2 - bD^2 = 1$. $(x_0 + y_0 \sqrt D) (x_0
- y_0 \sqrt D) = x_0^2 - Dy^2 = 1$, so $x_0 - y_0 \sqrt D > 0$. 

So 

\begin{align*}
(x_0+y_0\sqrt D)^n (x_0-y_0\sqrt D)^n &\le (x+y\sqrt D)(x_0-y_0\sqrt
D)^n \\
&\le (x_0 + y_0 \sqrt D)^{n+1} (x_0 - y_0 \sqrt D)^n.
\end{align*}

Divide through to get $1 \le a+b \sqrt D < x_0 + y_0 \sqrt D$. So either
$a+b\sqrt D = 1$, or it leads to a solution less than the minimal one. 

$(a+b\sqrt D)(a-b\sqrt D)=a^2-Db^2 = 1$; $a+b \sqrt D \ge 1$, so $0 <
a+b \sqrt D \le 1$. 

In particular, we have $a-b\sqrt D \le 1 < a+b \sqrt D$, so $b \ge 0$.
$a-b\sqrt D > 0$, so $a>0$.  If $b>0$, then $b \ge y_0$ to avoid violating
minimality, so $a^2=1+b \sqrt D \ge 1+y_0^2D = x_0D$, making $a \ge x_0$.
But the last inequality was strict.

So $a=1, b=0$.

\end{proof}

%% this is lecture fifteen

So we know how to find a complete set of solutions given one. But we haven't
yet proved that there is one - which is what the next theorem is for.

\begin{thm}
\label{pell}
If $D \in \N$ is not a square, $x^2 - Dy^2 = 1$ has solutions in integers.
\end{thm}

This is not an obvious theorem; for $D\le 50$, there are 43 non-square numbers,
only 41 of which have solutions to this with $y<1000$. With $D=151$, the
minimal solution is $x=1728148040, y=140634693$. Nonetheless, it's true.

\begin{lemma}
There are infinitely many solutions to $|x^2-Dy^2| < 1+2\sqrt D$ with $x,y$
coprime
\end{lemma}
\begin{proof}

Suppose the set of solutions $S$ were finite.

For each solution (except for the trivial one $(1,0)$), $\frac xy \in
\Q$, whilst $\sqrt D \not \in \Q$. So $|\sqrt D - \frac xy|$ is strictly
positive $\forall x,y \in S$. 

Choose $L \in \N$ with $|\sqrt D - \frac xy| \ge \frac 1L$ for all the
solutions.  Now apply theorem \ref{dirichlet_approximation} (Dirichlet's
approximation theorem) to get $u,v \in \N$ with $v \le L$, $\sqrt D -
\frac uv \le \frac 1{v(L+1)} < \frac 1L$, $u,v$ coprime, and $(u,v) \not
\in S$ by definition of $L$. 

But $|\sqrt D - \frac uv| \le \frac 1 {v^2}$ since $v<L$, so

$$|\sqrt D - \frac uv| = |2 \sqrt D + (\frac uv - \sqrt D) \le 2 \sqrt D +
|\sqrt D - \frac uv| \le 2 \sqrt D + 1.$$

So $$|D-\frac{u^2}{v^2}| = (\sqrt D - \frac uv) (\sqrt D + \frac uv) \le
\frac {2 \sqrt D +1}{v^2}.$$

So $v^2D - u^2 < 2 \sqrt D +1$, so $(u,v)$ satisfies the conditions to be in
$S$ but isn't there - but $S$ contains all the solutions. Contradiction.
\end{proof}

\begin{proof}[Proof of theorem \ref{pell}]

By the lemma, there is at least one $k$ such that $x^2 - Dy^2 = k$ has
infinitely many solutions with $(x,y)=1$. 

We divide these solutions into $k^2$ classes according to the residues
of $x$ and $y$ modulo $k$; at least one of these classes must be
infinite, so in particular it must have $\ge 2$ elements. So take
different solutions $(x,y)$ and $(x',y')$ in the same class; $x, x' = i
\pmod k$, $y,y' = j \pmod k$. 

$$((xx'-Dyy')^2 - D (xy'-yx')^2 = (x^2-Dy^2)({x'}^2-D{y'}^2) = k^2.$$

$xy'-yx' \equiv ij-ji=0 \pmod k$, and $xx'-Dyy' \equiv i^2-Dj^2 \equiv
x^2-Dy^2 \equiv 0 \pmod k$. So, writing $xx'-Dyy'=kx^*$ and
$xy'-yx'=ky^*$, we have ${x^*}^2 - D{y^*}^2 = 1$. 

So we've got a solution, unless $y^* = 0$. But, in that case, $xy' =
yx'$.  But $x$ and $y$ are coprime, so $y | xy' \implies y | y'$. The
same argument gives $y' | y$, so $y=y'$, and also $x=x'$ - but we chose
them to be different. So the argument can't fail in that way

\end{proof}

That result is very nearly a constructive argument, given an algorithm for
finding the approximation whose existence is known from Dirichlet's lemma.

On the other hand, there are better algorithms for this problem, involving
the continued-fraction expression of the square root.

\subsection{Mordell's Equation}

Mordell's Equation is $x^2 + k = y^3$ for $x,y \in \Z$ and $k$ given.

We've already demonstrated that there are no solutions for $k=7$ (in
theorem \ref{x^2+7}). It turns out there are finitely many solutions for
each $k$, and Baker has produced what must be one of the most useless
theorems ever :

\begin{thm}[Baker's Bound]
If $x^2+k=y^3$, then $$\max(|x|, |y|) < \exp(10^{10} {|k|}^{10000}).$$
\end{thm}

Fermat proved that $x^2+2=y^3$ has solution $x=\pm 5, y=3$, and that
$x^2+4=y^3$ has solutions $x=\pm 2, y=2$ and $x=\pm 11, y=5$. We'll prove

\begin{thm}
$x^2+1=y^3$ has only the trivial solution $x=0, y=1$.
\end{thm}

\begin{proof}

Working mod 8 gives that $y$ must be odd and positive, and $x$ even.

Recall theorem \ref{sumoftwosquares} : `if $n \in \N$ divides $N^2+1$ then
$n$ may be written as $a^2+b^2$ with $a \equiv Nb \pmod n$'. Here, $y|x^2+1$,
so $y=a^2+b^2$, with $a \equiv xb \pmod y$.

We will work in $\Z[i]$, though purely formally (that is, we won't have to use
unique factorisation). First, we prove that $x+i = \eta (a+bi)^3$ where $\eta$
is a unit of $\Z[i]$.

Set $(a+bi)^3 = p+qi$ ($p=a^3-3ab^2$, $q=3a^2b-b^3$). Now,

\begin{align*}
(a-bx)^3& = a^3 - 3a^2bx + 3ab^2x^2 -b^3x^3 \\
&= (a^3-3ab^2) + 3ab^2 (x^2+1) -(3a^2b-b^3)x - b^3x(1+x^2) \\
&\equiv p-qx \pmod {y^3}
\end{align*}

since $y^3=x^2+1$. But $y|a-bx \implies y^3 | (a-bx)^3 \implies y^3 | p-qx$.

Now, let $\frac {x+i}{(a+bi)^3} = \lambda \in \C$. $y \not =0$, so the division
will work.

\begin{enumerate}
\item $\lambda$ has integer real and imaginary parts.

\begin{align*}
(x+i)(p-qi)&= \lambda (a+bi)^3 (p-qi)\\
           &= \lambda (a+bi)^3 {\bar{a+bi}}^3 \\
           &= \lambda |a+bi|^3 = \lambda (a^2+b^2)^3 = \lambda y^3.
\end{align*}

Now, $(x+i)(p-qi) = xp+q+(p-qx)i$, and $y^3 | p-qx$, $xp+q \equiv xp-qx^2
\pmod {y^3} = x(p-qx) \equiv 0$.

So $$\lambda = m+ni = \frac{xp+q}{y^3} + \frac{p-qx}{y^3}i,$$
so $m$ and $n$ are integers.

\item $|\lambda|^2$=1

$$|x+i|^2 = x^2+1 = |\lambda|^2 |(a+bi)^3|^2 = |\lambda^2| (a^2+b^2)^3 = 
|\lambda^2| y^3.$$

So $|\lambda^2| = 1$, since $x^2+1=y^3$.

\end{enumerate}

So $x+i = \eta (a+bi)^3$. $\eta^4=1$ since $\eta^2 = \pm 1$, so $\eta^9
=\eta$. So $x+i = (\eta^3 (a+bi))^3$. Let $\alpha + \beta i = \eta^3
(a+bi)$. Then $x+i = (\alpha + \beta i)^3$. 

So $x = \alpha^3 - 3\alpha \beta^2$ and $1 = 3\alpha^2 \beta - \beta^3 =
\beta(3 \alpha^2 - \beta^2)$. So $\beta | 1$, so $\beta = \pm 1$. So
$3 \alpha^2 - \beta^2 = \pm 1$. $\beta^2=1$, so $3 \alpha^2 = 0$ or $2$.
But $\alpha \in \Z$, so $\alpha=0$.

So $(x,y) = (0,1)$.

\end{proof}

%% this is lecture sixteen

\section{More on primes}

Some time ago, we defined $\pi(x)$ as the number of primes $\le x$. The
Prime Number Theorem states that $\pi(x) \sim \frac{x}{\log x}$; it is
quite hard to prove the exact statement, but there are elementary proofs
that $\pi(x) = O(\frac x {\log x})$. 

\subsection{A lower bound for $\pi(x)$}

\begin{thm}
\label{pi_lower}
For $x \ge 3$, we have $$\pi(x) \ge \frac {(x-3) \log 2}{\log x}.$$
\end{thm}

To prove this, we show that $$\pi(2n+1) \ge \frac{2n \log 2}{\log
(2n+1)};$$ then, for $x \ge 3$, we let $2n+1$ be the largest odd number
$\le x$ with $n \ge 1$; $$\pi(x) \ge \pi(2n+1) \ge \frac{2n \log 2}{\log
x} \ge \frac {(x-3) \log 2}{\log x}$$ since $2n+3 \ge x$, so $2n \ge
x-3$. 

\begin{proof}

Let $$I = \int_0^1 x^n (1-x)^n \rm{d}x,$$ a function we've seen before.
Using the binomial theorem, we have

$$I = \int_0^1 \sum_{r=0}^n (-1)^r \binom nr x^{n+r} {\rm d}x =
\sum_{r=0}^n (-1)^r \binom nr \frac 1 {n+r+1}$$

Now, set $d_k = \lcm (1 \ldots k)$ (for example, $d_7 = 420$). So
$d_{2n+1}I$ is an integer since the denominators of each of the summands
divide $d_{2n+1}$. 

$x^n(1-x)^n$ has a maximum value of $4^{-n}$ at $x=\frac 12$, so
$I<4^{-n}$.  So $$0 < d_{2n+1}I < \frac{d_{2n+1}}{4^n}.$$

But $d_{2n+1}I$ is a positive integer, so at least $1$, so $d_{2n+1} \ge
4^n$. 

If $p$ is prime, and $p^a | d_{2n+1}$, $p^{a+1} \not | d_{2n+1}$, then
$\exists m \le 2n+1 : p^a | m$. So $p^a \le 2n+1$. 

So $$4^n \le d_{2n+1} = \prod_{p_i^{e_i} \le 2n+1} p_i^{e_i} \le
(2n+1)^{\pi(2n+1)}.$$

Taking logs, we have

$$n \log 4 \le \log(d_{2n+1}) \le \pi(2n+1) \log(2n+1)$$

Dividing through, and discarding the $d_{2n+1}$ term as having served
its purpose, we have

$$\pi(2n+1) \ge \frac {2n \log 2} {\log(2n+1)}$$

\end{proof}

\subsection{An upper bound for $\pi(x)$}

As is fairly common in number theory, we start off with something superficially
completely different.

\begin{defn}
$\theta(x) = \sum_{p \le x} \log p$
\end{defn}

\begin{thm}
$\theta(x) \le x \log 4$
\end{thm}

\begin{proof}

Set $$M = \binom{2m+1}{m} = \frac {(2m+1)(2m)(2m-1) \ldots (m+2)}{m!}.$$

This is divisible by every prime between $m+2$ and $2m+1$, and is an integer.
So $\prod_{m+1 < p \le 2m+1} p | M$, so that product is $\le M$. Taking logs
gives $$\theta(2m+1)-\theta(m+1) \le \log M.$$

Now consider expanding $(1+1)^{2m+1}$ by the binomial theorem, to get

$$2 \cdot 4^m = 2^{2m+1} = \sum_{i=0}^{2m+1} \binom{2m+1}{i} \ge
\binom{2m+1}{m} + \binom{2m+1}{m+1} = 2 M.$$

So we have $\theta(2m+1)-\theta(m+1) \le m \log 4$. All we need do now
is work by induction to get the form required by the problem. 

Since $\theta(x) = \theta([x])$, we can confine ourselves to integer
$x$. We work by induction; for $n=1$ we have $0 \le 2 \log 2$, $n=2$
gives us $\log 2 \le 4 \log 2$, which is a start. 

Suppose the result holds for all $n < n_0$, and consider $n_0$. 

If $n_0$ is even, it's composite, so $\theta(n_0) = \theta(n_0-1) \le
2(n_0-1) \log 2 \le 2 n_0 \log 2$. 

If $n_0$ is odd, write $n_0 = 2m+1$. Then

\begin{align*}
\theta(n_0)& = \theta(2m+1)\\
&= \theta(2m+1) - \theta(m+1)+\theta(m+1)\\
&\le 2m \log 2 + 2 (m+1) \log 2\\
&\le 2 (2m+1) \log 2 = 2 n_0 \log 2.
\end{align*}

\end{proof}

Before we can use that result to provide a bound for $\pi(x)$, we need
the following

\begin{lemma}

For $x>1$, we have 

\begin{enumerate}

\item $$\frac{\log x}x \le 1/e$$
\item $$\sqrt x \le \frac{2x}{e \log x}$$

\end{enumerate}
\end{lemma}
\begin{proof}

\begin{enumerate}
\item Differentiate; the function has a maximum at $x=e$, value $1/e$.

\item Put $t = \sqrt x$ and apply the previous part to get $\frac{\log
\sqrt x}{\sqrt x} \le 1/e$. So $\frac{\log x}{2 \sqrt x} \le 1/e$;
multiply by $x$ and rearrange to get $\sqrt x \le \frac {2x}{e \log x}$.
\end{enumerate}

\end{proof}

We have that $\theta(x) - \theta(\sqrt x) \le \theta(x) \le 2x
\log 2$. But the first term can be written in terms of $\pi(x)$ by: 

\begin{align*}
\theta(x) - \theta(\sqrt x)& = \sum_{\sqrt x \le p \le x} p\\
&\le \sum_{\sqrt x \le p \le x} \log \sqrt x \\
&= (\pi(x) - \pi(\sqrt x)) \log \sqrt x
\end{align*}

So, $$\pi(x) - \pi(\sqrt x) \le \frac{\theta(x)}{\log{\sqrt x}} \le \frac
{2x \log 2}{\log \sqrt x} = \frac {4x \log 2}{\log x}.$$

And the remainder is bounded above by something of the right form since
$$\pi(\sqrt x) \le \sqrt x \le \frac {2x}{e \log x}.$$

So $$\pi(x) \le (4 \log 2 + 2/e) \frac x {\log x} \le 3.51 \frac x
\log x.$$

So $\pi(x) = O(\frac x {\log x})$, with the constant lying between $\log
2$ and $3.51$. 

\subsection{An upper bound for $p_n$}

\begin{thm}
The $n$th prime number, $p_n$, satisfies $p_n < n^2$.
\end{thm}

\begin{proof}
By experiment, the result holds for $n < 8$.

$p_n$ is odd, so we'll write $p_n = 2k+1$; now use theorem \ref{pi_lower},
and the knowledge that $\pi(p_n) = n$, to get

$$n \ge \frac {2k \log 2}{\log p_n} = \log 2 \frac {p_n-1}{\log p_n}.$$

Now, taking derivatives shows that $\frac{\log x}{x-1}$ is decreasing for
$x \ge 3$, so $\frac {x-1}{\log x}$ is increasing. To obtain a contradiction,
assume $p_n \ge n^2$. Then

$$\frac{p_n-1}{\log p_n} \ge \frac {n^2-1}{\log n^2} = \frac{n^2-1}{2
\log n}.$$

So 

\begin{align*}
n \ge \frac {(n^2-1) \log 2}{2 \log n}& \implies n+1 \ge \frac{(n^2-1) \log 2}{2 \log n} \\
& \implies 1 \ge \frac {(n-1)\log 2}{2 \log n} \ge \frac{(8-1) \log 2}{2 \log 8}
\end{align*}

since the function is decreasing. But the right-hand side is equal to $7/6$;
this is the desired contradiction.
\end{proof}

\end{document}