main.tex

\def\module{M3P14 Number Theory}
\def\lecturer{Prof Toby Gee}
\def\term{Autumn 2018}
\def\cover{
\begin{align*}
\pi
& = 3 + \cfrac{1}{7 + \cfrac{1}{15 + \cfrac{1}{1 + \cfrac{1}{292 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{\ddots}}}}}}}} \\
& = 0 + \cfrac{4}{1 + \cfrac{1^2}{2 + \cfrac{3^2}{2 + \cfrac{5^2}{\ddots}}}}
= 0 + \cfrac{4}{1 + \cfrac{1^2}{3 + \cfrac{2^2}{5 + \cfrac{3^2}{\ddots}}}}
= 3 + \cfrac{1^2}{6 + \cfrac{3^2}{6 + \cfrac{5^2}{6 + \cfrac{7^2}{\ddots}}}} \\
& = 2 + \cfrac{2}{\tfrac{1}{1} + \cfrac{1}{\tfrac{1}{2} + \cfrac{1}{\tfrac{1}{3} + \cfrac{1}{\ddots}}}}
= 2 + \cfrac{2}{1 + \cfrac{1 \cdot 2}{1 + \cfrac{2 \cdot 3}{1 + \cfrac{3 \cdot 4}{\ddots}}}}
= 2 + \cfrac{4}{3 + \cfrac{1 \cdot 3}{4 + \cfrac{3 \cdot 5}{4 + \cfrac{5 \cdot 7}{\ddots}}}} \\
& = 3 + \cfrac{1^3}{6 + \cfrac{1^3 + 2^3}{6 + \cfrac{1^3 + 2^3 + 3^3 + 4^3}{6 + \cfrac{1^3 + 2^3 + 3^3 + 4^3 + 5^3 + 6^3}{6 + \cfrac{1^3 + 2^3 + 3^3 + 4^3 + 5^3 + 6^3 + 7^3 + 8^3}{\ddots}}}}}
\end{align*}
}
\def\syllabus{Prime numbers and factorisation. Euclid's algorithm and consequences. Congruences. The structure of $ \unit{n} $. Primality testing and factorisation. RSA algorithm. Quadratic reciprocity. Sums of squares. Pell's equation. Continued fractions. Diophantine approximation. Primes in arithmetic progressions. Arithmetic functions. The distribution of prime numbers.}

\input{header}

\begin{document}

\input{cover}

\section{Introduction}

\lecture{1}{Friday}{05/10/18}

Roughly speaking number theory is the study of the integers. More specifically, problems in number theory often have a lot to do with primes and divisibility, congruences, and include problems about the rational numbers. For example, solving equations in integers or in the rationals, such as $ x^2 - 2y^2 = 1 $, etc. We will be looking at problems that can be tackled by elementary means, but this does not mean easy. Also the statements of problems can be elementary without the solution being elementary, such as Fermat's last theorem, or even known, such as the twin prime conjecture. Sometimes we will state interesting things, like the prime number theorem, without proving them. Typically these will be things that we could prove if the course was much longer. We will start the course with a look at prime numbers and factorisation, a review of Euclid's algorithm and consequences, congruences, the structure of $ \unit{n} $, RSA algorithm, and quadratic reciprocity. We will return to primes at the end, too. The following are typical questions here.
\begin{itemize}
\item How do you tell if a number is prime?
\item How many primes are there congruent to $ a \mod b $ for given $ a $ and $ b $?
\item How many primes are there less than $ n $?
\end{itemize}
A warning is that we will be using plenty of things from the compulsory first and second year algebra courses, about groups, rings, ideals, fields, Lagrange's theorem, the first isomorphism theorem, and so on. You may want to revise this material if you are not comfortable with it. The course is not based on any particular book, although some material, such as continued fractions, was drawn from the following.
\begin{itemize}
\item A Baker, A concise introduction to the theory of numbers, 1984
\end{itemize}
Not everything we will do is in that book, though.

\pagebreak

\section{Euclid's algorithm and unique factorisation}

\subsection{Divisibility}

\begin{definition}
If $ a, b \in \ZZ $, we say that $ a $ \textbf{divides} $ b $, and $ a \mid b $, if there exists $ c \in \ZZ $ such that $ b = ac $. If $ a $ does not divide $ b $, write $ a \nmid b $.
\end{definition}

If $ a \mid b $ and $ a \mid c $ then $ a \mid rb + sc $ for any $ r, s \in \ZZ $.

\begin{definition}
The \textbf{greatest common divisor (gcd)} or \textbf{highest common factor (hcf)} of $ a $ and $ b $ is the largest positive integer dividing $ a $ and $ b $. Write it as $ \br{a, b} $.
\end{definition}

\begin{example*}
$ \br{-10, 15} = 5 $.
\end{example*}

\begin{note*}
The ring $ \ZZ $ is a principal ideal domain (PID). If $ f_1, \dots, f_n \in R $, write $ \br{f_1, \dots, f_n} $ for the ideal generated by the $ f_i $. Then for $ a, b \in \ZZ $, the ideal $ \br{a, b} $ is generated by the gcd $ \br{a, b} $, by Theorem \ref{thm:6} below.
\end{note*}

\begin{definition}
$ n \in \ZZ $ is \textbf{prime} if $ n $ has exactly two positive divisors, namely $ 1 $ and $ n $.
\end{definition}

\begin{note*}
Frequently when people talk about prime numbers they restrict to the positive case. If we write, let $ p $ be a prime number, then we will usually mean $ p > 0 $.
\end{note*}

\begin{note*}
$ 1 $ is not prime.
\end{note*}

\subsection{Euclid's algorithm}

\begin{proposition}
If $ a, b \in \ZZ $, not both zero, then for any $ n \in \ZZ $, $ \br{a, b} = \br{a, b - na} $.
\end{proposition}

\begin{proof}
By definition, it is enough to show that if $ r \mid a $ and $ r \mid b $ then $ r \mid a $ and $ r \mid b - na $ and conversely.
\end{proof}

\begin{theorem}
\label{thm:5}
Let $ a, b \in \ZZ $ with $ b > 0 $. Then there exist unique $ q, r \in \ZZ $ with $ 0 \le r < b $ and $ a = qb + r $.
\end{theorem}

\begin{proof}
Take $ q = \fbr{a / b} $. By definition $ 0 \le a / b - q < 1 $, that is $ 0 \le a - qb < b $, so take $ r = a - qb $. Uniqueness is easy.
\end{proof}

\textbf{Euclid's algorithm} is as follows. Let $ a, b \in \ZZ $ not both zero. Without loss of generality, $ 0 \le b \le a $.
\begin{enumerate}[leftmargin=0.5in, label=Step \arabic*.]
\item If $ b = 0 $, output $ a $.
\item Otherwise, replace $ \br{a, b} $ with $ \br{b, r} $ as in Theorem \ref{thm:5}. Then go to step 1.
\end{enumerate}
This algorithm terminates because $ \abs{a} + \abs{b} $ decreases when we apply step $ 2 $.

\begin{example*}
\hfill

\begin{minipage}{0.5\textwidth}
\begin{align*}
\br{120, 87}
& = \br{87, 33} & 120 = 87 + 33 \\
& = \br{33, 21} & 87 = 2\br{33} + 21 \\
& = \br{21, 12} & 33 = 21 + 12 \\
& = \br{12, 9} & 21 = 12 + 9 \\
& = \br{9, 3} & 12 = 9 + 3 \\
& = \br{3, 0} & 9 = 3\br{3} + 10.
\end{align*}
\end{minipage}
\begin{minipage}{0.4\textwidth}
\begin{align*}
3
& = 12 - 9 \\
& = 12 - \br{21 - 12} \\
& = 2\br{12} - 21 \\
& = 2\br{33 - 21} - 21 \\
& = 2\br{33} - 3\br{21} \\
& = 2\br{33} - 3\br{87 - 2\br{33}} \\
& = 8\br{33} - 3\br{87} \\
& = 8\br{120 - 87} - 3\br{87} \\
& = 8\br{120} - 11\br{87}.
\end{align*}
\end{minipage}
\end{example*}

\begin{theorem}
\label{thm:6}
If $ a, b \in \ZZ $, not both zero, then there exist $ r, s \in \ZZ $ such that $ \br{a, b} = ra + sb $.
\end{theorem}

\begin{proof}
Idea is to write $ \br{a_n, b_n} $ for the sequence of pairs in Euclid's algorithm, and use downwards induction on $ n $. \footnote{Exercise}
\end{proof}

\pagebreak

\subsection{Unique factorisation}

\begin{proposition}
\label{prop:7}
Let $ n, a, b \in \ZZ $ with $ n \mid ab $ and $ \br{n, a} = 1 $. Then $ n \mid b $.
\end{proposition}

\begin{proof}
Since $ \br{n, a} = 1 $, we can write $ rn + sa = 1 $, so $ b = n\br{rb} + \br{ab}s $, which is divisible by $ n $.
\end{proof}

If $ \br{n, a} = 1 $, we say that $ n $ and $ a $ are \textbf{coprime}.

\lecture{2}{Tuesday}{09/10/18}

\begin{corollary}
\label{cor:8}
If $ p $ is prime and $ p \mid ab $ then $ p \mid a $ or $ p \mid b $.
\end{corollary}

\begin{proof}
If $ p \nmid a $ then $ \br{p, a} = 1 $, so Proposition \ref{prop:7} implies $ p \mid b $.
\end{proof}

\begin{proposition}
\label{prop:9}
If $ \br{a, b} = 1 $, and $ a \mid n $ and $ b \mid n $, then $ ab \mid n $.
\end{proposition}

\begin{proof}
By \ref{thm:6}, we can write $ 1 = ra + sb $ with $ r, s \in \ZZ $. So $ n = r\br{na} + s\br{nb} $, which is divisible by $ ab $.
\end{proof}

We say that $ m_1, \dots, m_n \in \ZZ $ are \textbf{pairwise coprime} if $ \br{m_i, m_j} = 1 $ for all $ i \ne j $.

\begin{corollary}
\label{cor:10}
If $ m_1, \dots, m_n $ are pairwise coprime and $ m_i \mid N $ for all $ i $ then $ m_1 \dots m_n \mid N $.
\end{corollary}

\begin{proof}
Induction on $ n $, where $ n = 2 $ is Proposition \ref{prop:9}. \footnote{Exercise}
\end{proof}

\begin{proposition}
\label{prop:11}
Every $ n \in \ZZ^* $ can be written as $ \pm p_1 \dots p_r $ where $ p_i $ are prime, and $ r $ could be zero.
\end{proposition}

\begin{proof}
Use induction on $ \abs{n} $. The case $ \abs{n} $ is trivial, so suppose $ \abs{n} > 1 $. Then either $ \abs{n} $ is prime, or $ \abs{n} = ab $ for $ 1 < a, b < \abs{n} $, and by induction each of $ a $ and $ b $ is a product of primes.
\end{proof}

\begin{theorem}
Every $ n \in \ZZ_{> 0} $ can be written as $ \pm p_1 \dots p_r $ where $ p_i $ are prime and are uniquely determined up to ordering.
\end{theorem}

\begin{proof}
Existence is Proposition \ref{prop:11}. Suppose that $ n = p_1 \dots p_r = q_1 \dots q_s $, with $ p_i $ and $ q_i $ prime. Then without loss of generality suppose $ r, s \ge 1 $. Then $ p_1 \mid p_1 \dots p_r $, so $ p_1 \mid q_1 \dots q_s $. By Corollary \ref{cor:8}, either $ p_1 \mid q_1 $ or $ p_1 \mid q_2 \dots q_s $. Proceeding inductively, eventually $ p_1 \mid q_i $ for some $ i $. Since $ q_i $ is prime this means $ p_1 = q_i $. We then have $ p_2 \dots p_r = q_1 \dots q_{i - 1}q_{i + 1} \dots q_s $. Since this product is smaller than $ n $, by the inductive hypothesis we must have $ r - 1 = s - 1 $ and the $ p_i $, except $ p_1 $, are a rearrangement of the $ q_j $, except $ q_i $.
\end{proof}

\subsection{Linear diophantine equations}

Let $ a, b, c \in \ZZ^* $. Want to solve
$$ ax + by = c, \qquad x, y \in \ZZ. $$

\begin{example*}
$ 2x + 6y = 3 $ has no solutions.
\end{example*}

In general, there are no solutions if $ \br{a, b} \nmid c $. Suppose that $ \br{a, b} \mid c $. Then
$$ ax + by = c \qquad \iff \qquad \dfrac{a}{\br{a, b}}x + \dfrac{b}{\br{a, b}}y = \dfrac{c}{\br{a, b}}. $$
By Theorem \ref{thm:6}, since $ \br{a / \br{a, b}, b / \br{a, b}} = 1 $, we can find $ r, s \in \ZZ $ with $ ar / \br{a, b} + bs / \br{a, b} = 1 $, so
$$ \dfrac{a}{\br{a, b}}\br{\dfrac{rc}{\br{a, b}}} + \dfrac{b}{\br{a, b}}\br{\dfrac{sc}{\br{a, b}}} = \dfrac{c}{\br{a, b}}. $$
So $ x = rc / \br{a, b} $ and $ y = sc / \br{a, b} $ is a solution. Then $ X $ and $ Y $ is another solution if and only if
$$ \dfrac{a}{\br{a, b}}X + \dfrac{b}{\br{a, b}}Y = \dfrac{a}{\br{a, b}}x + \dfrac{b}{\br{a, b}}y \qquad \iff \qquad \dfrac{a}{\br{a, b}} \ \Bigg| \ y - Y, \qquad \dfrac{b}{\br{a, b}} \ \Bigg| \ X - x. $$
See that the solutions are exactly
$$ X = x + \dfrac{nb}{\br{a, b}}, \qquad Y = y - \dfrac{na}{\br{a, b}}. $$

\pagebreak

\section{Congruences and modular arithmetic}

\subsection{Congruences}

\begin{definition}
Let $ n \in \ZZ^* $, usually $ n > 0 $. Let $ a, b \in \ZZ $. We say that $ a $ is \textbf{congruent to $ b \mod n $} if and only if $ n \mid a - b $. Write $ a \equiv b \mod n $.
\end{definition}

$ \equiv $ is an equivalence relation, and we write $ \ZZ / n\ZZ $ for the equivalence classes, which is a ring.

\begin{example*}
If $ a \equiv b \mod n $ and $ c \equiv d \mod n $, then
$$ a + c \equiv b + d \mod n, \qquad ac \equiv bd \mod n. $$
\end{example*}

If $ a \in \ZZ $, we sometimes write $ \overline{a} $ for the image of $ a $ in $ \ZZ / n\ZZ $.

\begin{example*}
If $ n = 12 $, then $ \overline{25} = \overline{1} $.
\end{example*}

So every element of $ \ZZ / n\ZZ $ is equal to $ \overline{r} $ for some unique $ r \in \cbr{0, \dots, n - 1} $. We often write
$$ \ZZ / n\ZZ = \cbr{0, \dots, n - 1}. $$

\begin{example*}
If $ n = 6 $, we could write $ 3 + 4 = 1 $ and $ 3 \times 4 = 0 $.
\end{example*}

Let $ R $ be a commutative ring with unity. Then a \textbf{unit} of $ R $ is an element $ x $ such that there exists $ y \in R $ with $ xy = 1 $. Write $ R^\times $ for the set of units in $ R $. This is a group under multiplication.

\begin{example*}
\hfill
\begin{itemize}
\item $ \ZZ^\times = \cbr{\pm 1} $.
\item $ \QQ^\times = \QQ \setminus \cbr{0} = \cbr{x \in \QQ \st x \ne 0} $.
\end{itemize}
\end{example*}

We want to understand $ \unit{n} $. Which elements of $ \cbr{0, \dots, n - 1} $ are in $ \unit{n} $? If $ r \in \ZZ $ and $ r \in \unit{n} $ then there exists $ s \in \ZZ $ such that $ rs \equiv 1 \mod n $. This implies that $ \br{r, n} = 1 $. Conversely, if $ \br{r, n} = 1 $, then there exist $ x, y \in \ZZ $ such that $ rx + ny = 1 $, that is $ rx \equiv 1 \mod n $, that is $ r $ is a unit. So
$$ \unit{n} = \cbr{0 \le i < n \st \br{i, n} = 1}. $$

\begin{example*}
If $ p $ is a prime, then
$$ \unit{p} = \cbr{1, \dots, p - 1}. $$
So $ \ZZ / p\ZZ $ is a ring with the property that every non-zero element has a multiplicative inverse, so it is a field. Another equivalent way to see this is to check that $ p\ZZ $ is a maximal ideal of $ \ZZ $.
\end{example*}

Thus every non-zero congruence class modulo $ p $ is a unit.

\pagebreak

\subsection{Linear congruence equations}

\lecture{3}{Wednesday}{10/10/18}

Consider the question of solving
$$ ax \equiv b \mod c, \qquad a, b, c, x \in \ZZ. $$
This is equivalent to solving
$$ ax + cy = b, \qquad y \in \ZZ. $$
We saw yesterday that this has solutions if and only if $ \br{a, c} \mid b $. Furthermore, there is a unique solution modulo $ c / \br{a, c} $, because all the solutions are obtained by adding multiples of $ c / \br{a, c} $ to our given $ x $, and subtracting the corresponding multiple of $ a / \br{a, c} $ from $ y $. This implies that there are $ \br{a, c} $ solutions to the original congruence modulo $ c $. If $ x_0 $ is one solution, the others are
$$ x_0 + \dfrac{cj}{\br{a, c}}, \qquad 0 \le j < \br{a, c}. $$
In particular, if $ \br{a, c} = 1 $ then there is a unique solution to $ ax \equiv b \mod c $. Indeed $ a \in \unit{c} $, so it has an inverse $ a^{-1} $, and $ x \equiv a^{-1}b \mod c $ is the unique solution.

\begin{example*}
\hfill
\begin{itemize}
\item $ 2x \equiv 3 \mod 6 $ has no solutions as $ \br{2, 6} = 2 \nmid 3 $.
\item $ 2x \equiv 4 \mod 6 $ if and only if $ x \equiv 2 \mod 3 $, which has solutions $ x \equiv 2 \mod 6 $ and $ x \equiv 5 \mod 6 $.
\end{itemize}
\end{example*}

\subsection{The Chinese remainder theorem}

\begin{theorem}[Chinese remainder theorem]
\label{thm:14}
Let $ m_1, \dots, m_n \in \ZZ_{> 0} $ be pairwise coprime. Then the natural map
$$ \ZZ / m_1 \dots m_n\ZZ \xrightarrow{\sim} \ZZ / m_1\ZZ \times \dots \times \ZZ / m_n\ZZ $$
is an isomorphism of rings. Consequently,
$$ \unit{m_1 \dots m_n} \xrightarrow{\sim} \unit{m_1} \times \dots \times \unit{m_n} $$
is an isomorphism of abelian groups.
\end{theorem}

\begin{remark*}
This is false without the assumption that $ m_i $ pairwise coprime, such as $ m_1 = m_2 = 2 $.
\end{remark*}

\begin{proof}
The map
$$ \ZZ / m_1 \dots m_n\ZZ \to \ZZ / m_1\ZZ \times \dots \times \ZZ / m_n\ZZ $$
is a ring homomorphism between two rings of order, or cardinality, $ m_1 \dots m_n $. So to show that it is an isomorphism, it is enough to show that it is an injection, so we only need to check that the kernel is zero. So we need to know that if $ m_i \mid N $ for all $ i $, then $ m_1 \dots m_n \mid N $. This is Corollary \ref{cor:10}. For the second part, just use that if $ R $ and $ S $ are rings, then
$$ \br{R \times S}^\times \cong R^\times \times S^\times. $$
\end{proof}

The first part says that given any $ a_i \in \ZZ $, there is a unique $ x \mod m_1 \dots m_n $ with $ x \equiv a_i \mod m_i $. Write
$$ M = m_1 \dots m_n, \qquad M_i = \dfrac{M}{m_i}. $$
Choose $ q_i $ such that $ q_iM_i \equiv 1 \mod m_i $, using $ \br{M_i, m_i} = 1 $ because $ \br{m_j, m_i} = 1 $ for all $ j \ne i $. Then take
$$ x = a_1q_1M_1 + \dots + a_nq_nM_n. $$
Then
$$ x \equiv a_iq_iM_i \equiv a_i \mod m_i. $$

\pagebreak

\section{The structure of \texorpdfstring{$ \unit{n} $}{Z/nZ}}

\subsection{The Euler \texorpdfstring{$ \Phi $}{Phi} function}

Let $ \Phi\br{n} $ be the order of $ \unit{n} $, that is
$$ \Phi\br{n} = \#\cbr{1 \le i < n \st \br{i, n} = 1}. $$

\begin{example*}
If $ p $ is prime, $ \Phi\br{p} = p - 1 $.
\end{example*}

$ \Phi $ is called \textbf{Euler's $ \Phi $ function}.

\begin{definition}
Let $ f $ be a function on the positive integers. Say that $ f $ is \textbf{strongly multiplicative} if
$$ f\br{mn} = f\br{m}f\br{n}, $$
for all $ m $ and $ n $. Say $ f $ is \textbf{multiplicative} if this holds whenever $ \br{m, n} = 1 $.
\end{definition}

$ \Phi $ is multiplicative by Theorem \ref{thm:14}, because if $ \br{m, n} = 1 $ then
$$ \unit{mn} \xrightarrow{\sim} \unit{m} \times \unit{n}. $$
$ \Phi $ is not strongly multiplicative, since $ \Phi\br{4} = 2 \ne 1 = \Phi\br{2}\Phi\br{2} $. Write $ n = \prod_i p_i^{a_i} $, where $ p_i $ are distinct primes. Then $ \Phi\br{n} = \prod_i \Phi\br{p_i^{a_i}} $. If $ p $ is prime then
$$ \Phi\br{p^a} = \#\cbr{1 \le i < p^a \st \br{i, p^a} = 1} = \#\cbr{1 \le i < p^a \st p \nmid i} = p^a - p^{a - 1} = p^a\br{1 - \dfrac{1}{p}}. $$
If $ n = \prod_i p_i^{a_i} $, then
$$ \Phi\br{n} = \prod_i \Phi\br{p_i^{a_i}} = \prod_i p_i^{a_i}\br{1 - \dfrac{1}{p_i}} = n\prod_i \br{1 - \dfrac{1}{p_i}} = n\prod_{p \mid n} \br{1 - \dfrac{1}{p}}. $$

\subsection{Euler's theorem}

\begin{theorem}[Euler's theorem]
\label{thm:16}
If $ \br{a, n} = 1 $, then
$$ a^{\Phi\br{n}} \equiv 1 \mod n. $$
\end{theorem}

\begin{proof}
This is equivalent to showing that $ \overline{a}^{\Phi\br{n}} = 1 $ in $ \unit{n} $. This is a group of order $ \Phi\br{n} $, so this is immediate from Lagrange's theorem.
\end{proof}

\begin{corollary}[Fermat's little theorem]
If $ p $ is prime and $ p \nmid a $, then
$$ a^{p - 1} \equiv 1 \mod p. $$
\end{corollary}

\begin{proof}
Theorem \ref{thm:16} with $ n = p $, so $ \Phi\br{n} = p - 1 $.
\end{proof}

Next, want to understand the structure of $ \unit{n} $. By Theorem \ref{thm:14}, it is enough to study the case that $ n $ is a prime power. We will begin by considering the case that $ n $ is prime.

\begin{example*}
Let $ n = 5 $. Then$ \unit{5} = \cbr{1, 2, 3, 4} $. This has order four. So it is either cyclic of order four or a product of two cyclic groups of order two. Since $ 2^2 = 4 $, $ 2^3 = 3 $, and $ 2^4 = 1 $, $ \unit{5} $ is cyclic of order four.
\end{example*}

Next, $ \unit{p} $ is cyclic of order $ p - 1 $ for any prime $ p $.

\lecture{4}{Friday}{12/10/18}

\begin{definition}
If $ G $ is a group and $ g \in G $ is an element, the \textbf{order} of $ g $ is the least $ a \ge 1 $ such that $ g^a = 1 $. In particular, if $ \br{g, n} = 1 $, then we write $ \ord_n g $ for the order of $ g $ in $ \unit{n} $, the \textbf{order of $ g $ modulo $ n $}.
\end{definition}

\begin{proposition}
\label{prop:19}
If $ G $ is a group and $ g $ is an element of order $ a $, then $ g^n = 1 $ if and only if $ a \mid n $.
\end{proposition}

\begin{proof}
If $ n = ab $ then $ g^n = \br{g^a}^b = 1^b = 1 $. Conversely, write $ n = ab + r $ with $ 0 \le r < a $. Then $ g^r = 1 $ and since $ r < a $ we have $ r = 0 $.
\end{proof}

\pagebreak

In particular, if $ \br{g, n} = 1 $, then $ g^{\Phi\br{n}} = 1 $, by Euler's theorem, so Proposition \ref{prop:19} implies that $ \ord_n g \mid \Phi\br{n} $. We want to prove that if $ p $ is prime, then $ \unit{p} $ is cyclic. Equivalently, we need to show that there exists $ g $ such that $ \ord_p g = \Phi\br{p} = p - 1 $. We will do this by counting the number of elements of each order. The key point is that $ \ZZ / p\ZZ $ is a field. For any $ d \ge 1 $, the elements of $ \unit{p} $ of order dividing $ d $ are exactly the roots of the $ X^d - 1 $ in $ \ZZ / p\ZZ $, by Proposition \ref{prop:19}.

\begin{example*}
The equation $ X^2 = 1 $ has exactly two solutions modulo $ p $ for any prime $ p $, namely $ \pm 1 $, but it can have more modulo $ n $ if $ n $ is composite. For example, if $ n = 15 $, then $ 4 $ and $ 11 $ are also solutions, since $ X^2 - 1 \equiv 0 \mod n $ if and only if $ n \mid \br{X + 1}\br{X - 1} $, for example $ 15 \mid \br{4 + 1}\br{4 - 1} $.
\end{example*}

\begin{definition}
$ g \in \ZZ $ with $ \br{g, p} = 1 $ is a \textbf{primitive root} if $ \ord_p g = p - 1 $, that is $ \unit{p} = \abr{g} $.
\end{definition}

\begin{lemma}
\label{lem:21}
Let $ R $ be a commutative ring, and let $ P\br{X} \in R\sbr{X} $. If $ \alpha \in R $ has $ P\br{\alpha} = 0 $, then there exists $ Q\br{X} \in R\sbr{X} $ such that $ P\br{X} = \br{X - \alpha}Q\br{X} $.
\end{lemma}

\begin{example*}
If $ R = \ZZ / 15\ZZ $, $ X^2 - 1 = \br{X + 1}\br{X - 1} = \br{X + 4}\br{X - 4} $.
\end{example*}

\begin{proof}
Induction on $ \deg P $, where $ \deg P = 0 $ is obvious. Let $ \deg P = d $, and assume the result holds for degree at most $ d - 1 $. Let $ P\br{X} = cX^d + \dots $ and $ S\br{X} = P\br{X} - cX^{d - 1}\br{X - \alpha} $. Then $ S\br{X} $ has degree at most $ d - 1 $. Also $ S\br{\alpha} = 0 $. By induction, we can write $ S\br{X} = \br{X - \alpha}R\br{X} $. Set $ Q\br{X} = cX^{d - 1} + R\br{X} $. Then $ \br{X - \alpha}Q\br{X} = cX^{d - 1}\br{X - \alpha} + S\br{X} = P\br{X} $.
\end{proof}

\begin{theorem}
\label{thm:22}
Let $ F $ be a field. Let $ P\br{X} $ be a polynomial in $ F\sbr{X} $. Then $ P\br{X} $ has at most $ d $ distinct roots in $ F $.
\end{theorem}

\begin{proof}
Induction on $ d = \deg P $, where $ d = 1 $ is obvious. If $ P $ has no roots, then we are done. Otherwise, let $ \alpha $ be a root. By Lemma \ref{lem:21}, $ P\br{X} = \br{X - \alpha}Q\br{X} $, and $ Q\br{X} $ has degree $ d - 1 $, so we are done by induction.
\end{proof}

\begin{corollary}
\label{cor:23}
Let $ d $ be any divisor of $ p - 1 $. Then there are exactly $ d $ elements of $ \unit{p} $ of order dividing $ d $.
\end{corollary}

\begin{proof}
We have to show that $ X^d - 1 $ has exactly $ d $ roots in $ \ZZ / p\ZZ $. By Fermat's little theorem, $ X^{p - 1} - 1 $ has exactly $ p - 1 $ roots. Since $ d \mid p - 1 $, we can write
$$ X^{p - 1} - 1 = \br{X^d - 1}\br{\br{X^d}^{\tfrac{p - 1}{d} - 1} + \dots + 1} = \br{X^d - 1}Q\br{X}, \qquad \deg Q = p - 1 - d. $$
Then $ X^{p - 1} - 1 $ has exactly $ p - 1 $ roots, $ X^d - 1 $ has at most $ d $ roots, and $ Q\br{X} $ has at most $ p - 1 - d $ roots, by Theorem \ref{thm:22}. So $ X^d - 1 $ has exactly $ d $ roots.
\end{proof}

\begin{example*}
Let $ p = 7 $. There are
\begin{itemize}
\item one element of order one,
\item two elements of order dividing two, so one element of order two,
\item three elements of order dividing three, so two elements of order three, and
\item six elements of order dividing six, so two elements of order six.
\end{itemize}
\end{example*}

\begin{lemma}
\label{lem:24}
For any $ n \ge 1 $, we have
$$ \sum_{d \mid n} \Phi\br{d} = n. $$
\end{lemma}

\begin{proof}
For each $ d \mid n $, the elements of $ \cbr{1, \dots, n} $ with $ \br{i, n} = n / d $ are exactly those of the form $ i = \br{n / d}j $ for $ 1 \le j \le d $ and $ \br{j, d} = 1 $. There are exactly $ \Phi\br{d} $ such elements. Since the $ n / d $ run over all the divisors of $ n $, we are done.
\end{proof}

\pagebreak

\begin{theorem}
\label{thm:25}
Let $ p $ be prime, and let $ d \mid p - 1 $. Then there are exactly $ \Phi\br{d} $ elements of $ \unit{p} $ of order $ d $. In particular, there are $ \Phi\br{p - 1} $ primitive roots, and $ \unit{p} $ is cyclic.
\end{theorem}

\begin{proof}
Induction on $ d $, where $ d = 1 $ is obvious. Assume the result holds for all $ d' \mid d $ and $ d' \ne d $. Then by Lemma \ref{lem:24},
$$ \Phi\br{d} = d - \sum_{d' \mid d, \ d' \ne d} \Phi\br{d'}. $$
Now use the inductive hypothesis and Corollary \ref{cor:23}.
\end{proof}

\lecture{5}{Tuesday}{16/10/18}

\begin{proposition}
Let $ p $ be an odd prime and $ n \ge 1 $. Then $ \unit{p^n} $ is cyclic.
\end{proposition}

\begin{proof}
Consider three cases.
\begin{itemize}[leftmargin=0.5in]
\item[$ n = 1 $.] Theorem \ref{thm:25}.
\item[$ n = 2 $.] Let $ g $ be a primitive root modulo $ p $. Claim that either $ g^{p - 1} \not\equiv 1 \mod p^2 $ and $ g $ is a generator for $ \unit{p^2} $, or $ g^{p - 1} \equiv 1 \mod p^2 $ and $ g + p $ is a generator for $ \unit{p^2} $. Either way, $ \unit{p^2} $ is cyclic. Suppose firstly that
$$ g^{p - 1} \not\equiv 1 \mod p^2. $$
Then $ \#\unit{p^2} = \Phi\br{p^2} = p\br{p - 1} $. So $ \ord_{p^2} g \mid p\br{p - 1} $. On the other hand, $ g^{\ord_{p^2} g} \equiv 1 \mod p^2 $, so $ g^{\ord_{p^2} g} \equiv 1 \mod p $, so $ p - 1 \mid \ord_{p^2} g $, because $ \ord_p g = p - 1 $ by assumption. But $ \ord_{p^2} g \ne p - 1 $, as $ g^{p - 1} \not\equiv 1 \mod p^2 $. So $ \ord_{p^2} g = p\br{p - 1} $, as required. Suppose now that
$$ g^{p - 1} \equiv 1 \mod p^2. $$
It suffices to show that $ \br{g + p}^{p - 1} \not\equiv 1 \mod p^2 $, as we can then apply the analysis above with $ g + p $ in place of $ g $. By the binomial theorem,
$$ \br{g + p}^{p - 1} \equiv g^{p - 1} + \br{p - 1}g^{p - 2}p \equiv 1 + \br{p - 1}g^{p - 2}p \mod p^2. $$
Since $ p \nmid \br{p - 1}g^{p - 2} $, $ \br{g + p}^{p - 1} \not\equiv 1 \mod p^2 $, as required.
\item[$ n \ge 2 $.] It suffices to show that if $ \ord_{p^2} g = p\br{p - 1} $, then $ \ord_{p^n} g = p^{n - 1}\br{p - 1} $. We do this by induction on $ n $. So assume that $ \ord_{p^n} g = p^{n - 1}\br{p - 1} $. Then $ \ord_{p^n} g \mid \ord_{p^{n + 1}} g $, and $ \ord_{p^{n + 1}} g \mid \Phi\br{p^{n + 1}} = p^n\br{p - 1} $. So either $ \ord_{p^{n + 1}} g = p^n\br{p - 1} $, or $ \ord_{p^{n + 1}} g = p^{n - 1}\br{p - 1} $. So we need to show that
$$ g^{p^{n - 1}\br{p - 1}} \not\equiv 1 \mod p^{n + 1}. $$
To do this, consider $ g^{p^{n - 2}\br{p - 1}} $ modulo $ p^{n - 1} $ and modulo $ p^n $. Since $ \Phi\br{p^{n - 1}} = p^{n - 2}\br{p - 1} $, by Euler's theorem, $ g^{p^{n - 2}\br{p - 1}} \equiv 1 \mod p^{n - 1} $. Write $ g^{p^{n - 2}\br{p - 1}} = 1 + p^{n - 1}t $. Since $ \ord_{p^n} g = p^{n - 1}\br{p - 1} $ by assumption, $ g^{p^{n - 2}\br{p - 1}} \not\equiv 1 \mod p^n $, that is $ p \nmid t $. Then
\begin{align*}
g^{p^{n - 1}\br{p - 1}}
& = \br{g^{p^{n - 2}\br{p - 1}}}^p
= \br{1 + p^{n - 1}t}^p
= 1 + p^nt + \binom{p}{2}p^{2\br{n - 1}}t^2 + \dots + p^{p\br{n - 1}}t^p \\
& \equiv 1 + p^nt \mod p^{n + 1},
\end{align*}
since $ r\br{n - 1} \ge n + 1 $ if and only if $ \br{r - 1}n \ge r + 1 $ and $ p > 2 $, so
$$ p^{n + 1} \ \Bigg| \ p^{2n - 1} = p^{2\br{n - 1} + 1} \ \Bigg| \ \binom{p}{2}p^{2\br{n - 1}}. $$
So $ g^{p^{n - 1}\br{p - 1}} \not\equiv 1 \mod p^{n + 1} $, because $ p \nmid t $.
\end{itemize}
\end{proof}

\begin{example*}
\hfill
\begin{itemize}
\item $ \unit{2} = \cbr{1} $.
\item $ \unit{4} = \cbr{1, 3} $ is cyclic of order two, with $ 3 $ as a generator.
\item $ \unit{8} = \cbr{1, 3, 5, 7} $ is not cyclic, since $ 1^2 \equiv 3^2 \equiv 5^2 \equiv 7^2 \equiv 1 \mod 8 $, so every element has order two.
\end{itemize}
\end{example*}

\pagebreak

\begin{lemma}
\label{lem:27}
For $ n \ge 0 $ we have
$$ 5^{2^n} \equiv 1 + 2^{n + 2} \mod 2^{n + 3}. $$
\end{lemma}

\begin{proof}
Induction on $ n $, where $ n = 0 $ is obvious. Assume that $ 5^{2^n} = 1 + 2^{n + 2}t $ with $ t $ odd. Then
$$ 5^{2^{n + 1}} = \br{1 + 2^{n + 1}t}^2 = 1 + 2^{n + 3}t + 2^{2\br{n + 2}}t^2 = 1 + 2^{n + 3}\br{t + 2^{n + 1}t^2}, $$
where $ t + 2^{n + 1}t^2 $ is odd.
\end{proof}

\begin{proposition}
If $ n \ge 2 $ then there is an isomorphism
$$ \unit{2^n} \xrightarrow{\sim} \ZZ / 2\ZZ \times \ZZ / 2^{n - 2}\ZZ. $$
In particular, if $ n \ge 3 $, then $ \unit{2^n} $ is not cyclic.
\end{proposition}

\begin{proof}
Let $ \abr{g} $ denote the group $ \cbr{1, \dots, g^{\ord g - 1}} $ generated by $ g $. Consider the natural map
$$ \abr{-1} \times \abr{5} \to \unit{2^n}. $$
This is injective, because if $ \pm 1\br{5}^s \equiv 1 \mod 2^n $ then in particular $ \pm 1\br{5}^s \equiv 1 \mod 4 $ so $ \pm 1 \equiv 1 \mod 4 $, so we must have $ 5^s \equiv 1 \mod 2^n $, that is $ 5^s = 1 $ in $ \abr{5} $. Then $ \abr{-1} $ has order $ 2 $ and $ \abr{5} $ has order $ \ord_{2^n} 5 = 2^{n - 2} $ by Lemma \ref{lem:27}. So $ \abr{-1} \times \abr{5} $ has order $ 2\br{2^{n - 2}} = 2^{n - 1} = \Phi\br{2^n} = \#\unit{2^n} $. So the map $ \abr{-1} \times \abr{5} \to \unit{2^n} $ is an injection of groups of the same order, so it is a bijection.
\end{proof}

\begin{theorem}
$ \unit{n} $ is cyclic if and only if either
\begin{itemize}
\item $ n = 1, 2, 4 $,
\item $ n = p^r $ for $ p > 2 $ prime and $ r \ge 1 $, or
\item $ n = 2p^r $ for $ p > 2 $ prime and $ r \ge 1 $.
\end{itemize}
\end{theorem}

\lecture{6}{Wednesday}{17/10/18}

Primitive roots are generators of $ \unit{n} $. Find them in practice by guessing small values of $ g $, and seeing if $ g $ is a generator. There are $ \Phi\br{p - 1} $ primitive roots, which means that you have a high probability of success. Could work out $ 1, \dots, g^{p - 2} $ and check these are distinct. This would be inefficient. Better is to check for some prime $ q \mid p - 1 $ whether $ g^{\br{p - 1} / q} = 1 $ or not. This works, because if $ g^{\br{p - 1} / q} = 1 $ then $ g $ is not a primitive root, while if $ g^{\br{p - 1} / q} \ne 1 $ then $ \ord_p g \mid p - 1 $ and $ \ord_p g \nmid \br{p - 1} / q $. If this holds for all $ q \mid p - 1 $, then $ \ord_p g = p - 1 $, because otherwise it would be a proper divisor, and so would divide $ \br{p - 1} / q $ for some prime $ q \mid p - 1 $.

\begin{example*}
Let $ p = 31 $, so $ p - 1 = 30 = \br{2}\br{3}\br{5} $. Then $ g $ is a primitive root if and only if
$$ g^{15} \ne 1, \qquad g^{10} \ne 1, \qquad g^{6} \ne 1. $$
\begin{itemize}
\item Is $ 2 $ a primitive root? $ 2^2 = 4, 2^4 = 16, 2^6 = 2 $, but $ 2^{10} = 2^{15} = 1 $ because $ 2^5 = 32 = 1 $.
\item How about $ 3 $? $ 3^2 = 9, 3^4 = 19, 3^6 = 16, 3^8 = 20, 3^{10} = 25, 3^{15} = 30 $. So $ 3 $ is a primitive root modulo $ 31 $.
\end{itemize}
\end{example*}

\pagebreak

\section{Primality testing and factorisation}

The idea is that testing whether $ n \in \ZZ $ is prime is easy. Factoring $ n $ is expected to be hard. Easy here means that there is an algorithm to check whether $ n $ is prime or not which runs in time polynomial in $ \log n $. It is known that a deterministic algorithm exists to do this, the \textbf{Agrawal-Kayal-Saxena (AKS) algorithm}, in 2005. We will see an algorithm that runs faster than this in practice. On the other hand, for factoring there are algorithms which are better than exponential in $ \log n $, but there is nothing close to polynomial time, and the general expectation is that no such algorithm should exist.

\subsection{Factorisation}

How do we factor three digit numbers, or small four digit numbers, say at most $ 400 $ if we wanted to factor with a paper or a calculator? If $ n \le 400 $ and $ n $ is composite, then it has a prime factor at most $ \sqrt{400} = 20 $, since if $ d \mid n $ then $ d\br{n / d} = n $, so either $ d \le \sqrt{n} $ or $ n / d \le \sqrt{n} $. So you only have to be able to check for divisibility by
$$ 2, \quad 3, \quad 5, \quad 7, \quad 11, \quad 13, \quad 17, \quad 19. $$
\begin{itemize}[leftmargin=0.75in]
\item[$ 2, 5 $.] Checking for divisibility is easy, by just looking at the last digit.
\item[$ 3, 11 $.] Use that $ 10 \equiv 1 \mod 3 $ and $ 10 \equiv -1 \mod 3 $. So
$$ \sum_i a_i10^i \equiv \sum_i a_i \mod 3, \qquad \sum_i a_i10^i \equiv \sum_i a_i\br{-1}^i \mod 11. $$
So you can check divisibility by $ 3 $, or $ 9 $, by checking for the sum of the digits, and $ 11 $ by taking the alternating sum.
\item[$ 7 $.] $ 10x + y \equiv 0 \mod 7 $ if and only if $ -2\br{10x + y} \equiv 0 \mod 7 $, if and only if $ x - 2y \equiv 0 \mod 7 $.
\item[$ 13, 17, 19 $.] There are no good tests.
\end{itemize}
If $ n \le 400 $ and $ n $ is not divisible by $ 2, 3, 5, 7, 11 $, then the smallest prime factor of $ n $ is at least $ 13 $. Since $ 13^3 > 400 $, it can have at most two prime factors. So if you want to factor numbers at most $ 400 $, you only have to remember a short list
$$ 13^2, \quad 13\br{17}, \quad 13\br{19}, \quad 13\br{23}, \quad 13\br{29}, \quad 17^2, \quad 17\br{19}, \quad 17\br{23}, \quad 19^2. $$

\begin{example*}
\hfill
\begin{itemize}
\item $ 143 \equiv 1 - 4 + 3 \equiv 0 \mod 11 $.
\item $ 144 \equiv 1 + 4 + 4 \equiv 0 \mod 9 $.
\item $ 154 \equiv 15 - 2\br{4} = 7 \equiv 0 \mod 7 $.
\end{itemize}
\end{example*}

\lecture{7}{Friday}{19/10/18}

Factor four digit numbers by an algorithm due to Fermat. The idea is to first check for small prime factors by hand, say $ p = 2, \dots, 19 $. If $ n $ is composite and does not have any small factors, then the prime factors of $ n $ should be close to $ \sqrt{n} $. If $ n = ab $ for $ a $ and $ b $ odd and $ a \le b $, then
$$ n = ab = \br{\dfrac{a + b}{2}}^2 - \br{\dfrac{b - a}{2}}^2, \qquad \br{\dfrac{a + b}{2}}^2 - n = \br{\dfrac{b - a}{2}}^2. $$
If you know $ \br{a + b} / 2 $ and $ \br{b - a} / 2 $, you can recover $ a $ and $ b $. So take $ m $ such that $ m^2 \le n < \br{m + 1}^2 $. If $ n = m^2 $, done. Otherwise check if $ \br{m + i}^2 - n $ is a square for increasing $ i $.

\begin{example*}
Let $ n = 6077 $. Then $ 77^2 < 6077 < 78^2 $, so
\begin{align*}
78^2 - 6077 & = 7, \\
79^2 - 6077 & = 164, \\
80^2 - 6077 & = 323, \\
81^2 - 6077 & = 484 = 22^2.
\end{align*}
Thus $ 6077 = 81^2 - 22^2 = \br{103}\br{59} $.
\end{example*}

\pagebreak

There exist algorithms for factoring $ n $ which run in better than exponential time in $ \log n $, such as the quadratic sieve and the general number field sieve.

\begin{example*}
Let $ n = 1649 $. Then $ 40^2 < 1649 < 41^2 $, so
\begin{align*}
41^2 - 1649 & = 32 = 2^5, \\
42^2 - 1649 & = 115, \\
43^2 - 1649 & = 200 = \br{2}^3\br{5}^2.
\end{align*}
Since $ 41^2 \equiv 2^5 \mod 1649 $ and $ 43^2 \equiv \br{2}^3\br{5}^2 \mod 1649 $,
$$ 80^2 \equiv \br{41}^2\br{43}^2 = 1763^2 \equiv 114^2 \mod 1649. $$
Then
$$ 0 \equiv 114^2 - 80^2 = \br{194}\br{34} = \br{2}^2\br{17}\br{97} \mod 1649. $$
In fact, $ 1649 = \br{17}\br{97} $. Better for this last step would be to have computed
$$ \br{194, 1649} = 97, \qquad \br{34, 1649} = 17. $$
Can do this quickly using Euclid's algorithm. To make this into an efficient algorithm, need to have a way given $ x_1, \dots, x_r $ to find a subset whose product is a square. If we know the prime factorisation for the $ x_i $, we can write
$$ x_i = p_1^{a_{i1}} \dots p_k^{a_{ik}}. $$
Want to choose $ \epsilon_i = 0, 1 $ such that $ \prod_{i = 1}^r x_i^{\epsilon_i} $ is a square. Equivalently, for each $ j $, want the exponent of $ p_j $ to be even, that is
$$ \sum_{i = 1}^r \epsilon_ia_{ij} \equiv 0 \mod 2. $$
Let
$$ x_1 = 2^5, \qquad x_2 = \br{5}\br{23}, \qquad x_3 = \br{2}^3\br{5}^2, \qquad p_1 = 2, \qquad p_2 = 5, \qquad p_3 = 23. $$
Ignore all numbers with a large prime factor, so here ignore $ 23 $. Then
$$ \onebytwo{\epsilon_1}{\epsilon_2}\twobytwo{5}{0}{3}{2} \equiv \onebytwo{0}{0} \mod 2 \qquad \iff \qquad \onebytwo{\epsilon_1}{\epsilon_2}\twobytwo{1}{0}{1}{0} = \onebytwo{0}{0} $$
in $ \ZZ / 2\ZZ $, a field $ \FF_2 $, that is $ \epsilon_1 + \epsilon_2 = 0 $, so $ \epsilon_1 = \epsilon_2 = 1 $.
\end{example*}

This step, solving linear equations in $ \ZZ / 2\ZZ $, can be done efficiently. The remaining difficulty is to find a supply of $ m \in \ZZ $ such that $ m^2 - n $ has only small prime factors. The idea is that if we fix a list of small primes to start with, we get congruence conditions on $ m $. It turns out that there is a straightforward algorithm for solving $ m^2 \equiv n \mod p $. This gives two possible values for $ m \mod p $. If you do this for lots of primes $ p $, you get a supply of congruence conditions for $ m $, so you can eliminate ever considering $ m $ such that $ m^2 - n $ has large prime factors.

\begin{example*}
$ m^2 = 1649 \equiv 2 \mod 3 $ has no solutions.
\end{example*}

\subsection{Testing primality}

\lecture{8}{Tuesday}{23/10/18}

Euler's theorem states that if $ \br{a, n} = 1 $ then $ a^{\Phi\br{n}} \equiv 1 \mod n $. In particular if $ p $ is prime then $ a^{p - 1} \equiv 1 \mod p $ for $ 1 \le a \le p - 1 $. In particular, if $ 2^{n - 1} \not\equiv 1 \mod n $, then $ n $ cannot be prime. The problem is that there exists $ n $ composite such that $ a^{n - 1} \equiv 1 \mod n $ for all $ \br{a, n} = 1 $, the \textbf{Carmichael numbers}. It is known that infinitely many of these exist. The \textbf{Miller-Rabin test} is a test for whether odd $ n \in \ZZ $ is prime or not. Today let $ n \equiv 3 \mod 4 $. Example sheet is $ n \equiv 1 \mod 4 $.

\begin{lemma}
\label{lem:30}
Let $ n > 1 $ be congruent to $ 3 \mod 4 $. Then $ n $ is prime if and only if
$$ a^{\tfrac{n - 1}{2}} \equiv \pm 1 \mod n, \qquad \br{a, n} = 1. $$
\end{lemma}

\pagebreak

\begin{proof}
\hfill
\begin{itemize}
\item If $ n $ is prime, then $ a^{n - 1} \equiv 1 \mod n $ by Fermat's little theorem, so $ \br{a^{\br{n - 1} / 2}}^2 \equiv 1 \mod n $, so $ a^{\br{n - 1} / 2} \equiv \pm 1 \mod n $.
\item Suppose firstly that $ n = p^k $ with $ p $ prime, and $ k \ge 2 $. Try
$$ a = 1 + p. $$
Then
$$ a^{\tfrac{n - 1}{2}} \equiv 1 + \br{\dfrac{n - 1}{2}}p \mod p^2, $$
by the binomial theorem. If $ a^{\br{n - 1} / 2} \equiv \pm 1 \mod n $, then
$$ \pm 1 \equiv a^{\tfrac{n - 1}{2}} \equiv 1 + \br{\dfrac{n - 1}{2}}p \equiv 1 \mod p, $$
so
$$ 1 \equiv 1 + \br{\dfrac{n - 1}{2}}p \mod p^2, $$
then $ p \mid \br{n - 1} / 2 $, so $ p \mid n - 1 $. But $ p \mid n $, a contradiction.
\item The remaining case is that $ n $ is composite but not a power of a prime. Write $ n = rs $ for $ r, s > 1 $, and odd, and $ \br{r, s} = 1 $. By the Chinese remainder theorem,
$$ \ZZ / n\ZZ \cong \ZZ / r\ZZ \times \ZZ / s\ZZ. $$
Choose $ a $ such that
$$ a \equiv -1 \mod r, \qquad a \equiv 1 \mod s. $$
Then $ \br{a, r} = \br{a, s} = 1 $, so $ \br{a, n} = 1 $. Since $ n \equiv 3 \mod 4 $, $ \br{n - 1} / 2 $ is odd, so
$$ a^{\tfrac{n - 1}{2}} \equiv -1 \mod r, \qquad a^{\tfrac{n - 1}{2}} \equiv 1 \mod s. $$
So $ a^{\br{n - 1} / 2} \not\equiv \pm 1 \mod n $.
\end{itemize}
\end{proof}

\begin{lemma}
\label{lem:31}
Suppose that $ n \equiv 3 \mod 4 $ is composite. Then the set of $ a \in \unit{n} $ which satisfy $ a^{\br{n - 1} / 2} \equiv \pm 1 \mod n $ is a proper subgroup of $ \unit{n} $.
\end{lemma}

\begin{proof}
Certainly $ 1^{\br{n - 1} / 2} \equiv 1 \mod n $. If $ a^{\br{n - 1} / 2} \equiv \pm 1 \mod n $ and $ b^{\br{n - 1} / 2} \equiv \pm 1 \mod n $,
$$ \br{ab}^{\tfrac{n - 1}{2}} \equiv a^{\tfrac{n - 1}{2}}b^{\tfrac{n - 1}{2}} \equiv \br{\pm 1}\br{\pm 1} \equiv \pm 1 \mod n, \qquad \br{a^{-1}}^{\tfrac{n - 1}{2}} \equiv \br{a^{\tfrac{n - 1}{2}}}^{-1} \equiv \br{\pm 1}^{-1} \equiv \pm 1 \mod n. $$
So this set is a subgroup of $ \unit{n} $. It is a proper subgroup by Lemma \ref{lem:30}.
\end{proof}

\begin{corollary}
At most half the elements of $ \unit{n} $ satisfy $ a^{\br{n - 1} / 2} \equiv \pm 1 \mod n $.
\end{corollary}

\begin{proof}
The set of such elements is a proper subgroup of $ \unit{n} $ by Lemma \ref{lem:31}, so it has index at least two.
\end{proof}

In fact, with a bit more work, you can improve this to show that at least $ \tfrac{3}{4} $ of the numbers $ 1 \le a \le n - 1 $ satisfy $ a^{\br{n - 1} / 2} \not\equiv \pm 1 \mod n $. So if you randomly choose numbers $ 1 \le a \le n - 1 $ $ x $ times, and $ n $ is composite, the probability that you find some $ a $ with $ a^{\br{n - 1} / 2} \not\equiv \pm 1 \mod n $ is at least $ 1 - \br{\tfrac{1}{4}}^x $. This gives a probabilistic algorithm to check if $ n $ is prime in polynomial time. If you assume the generalised Riemann hypothesis (GRH) you can find some
$$ 1 \le a \le \left\lceil 2 \br{\log n}^2 \right\rceil, \qquad a^{\tfrac{n - 1}{2}} \not\equiv \pm 1 \mod n. $$
In practice it is even better.

\begin{example*}
If $ n < 341550071728321 $, then one of $ a = 2, 3, 5, 7, 11, 13, 17 $ will work.
\end{example*}

\pagebreak

\section{Public-key cryptography}

Public-key cryptography is private communication and identity verification.

\subsection{Messages as sequences of classes modulo \texorpdfstring{$ n $}{n}}

How do we turn messages into numbers in $ \ZZ / n\ZZ $? The idea is to choose $ n $ very large. Say $ n > 2^{8k} $. Write down your message. Break it up into strings of at most $ k $ characters. Encode each character as an $ 8 $ bit binary number. String these integers together to get an $ 8k $ bit binary number. Regard that as an integer modulo $ n $.

\subsection{The Rivest-Shamir-Adleman (RSA) algorithm}

Now apply some function $ f : \ZZ / n\ZZ \to \ZZ / n\ZZ $, and then tell whoever you are trying to communicate with the result of this computation. Then they should apply some other function $ g : \ZZ / m\ZZ \to \ZZ / n\ZZ $, to get back the number you started with. So want $ f $ to be injective. Want to be able to make $ f $ public without making $ g $ public. The idea is to choose two large prime numbers $ p $ and $ q $ and set $ n = pq $. Choose $ \br{e, \Phi\br{n}} = 1 $. Find $ d $ such that
$$ de = 1 \mod \Phi\br{n} = \br{p - 1}\br{q - 1} = n - \br{p + q} + 1. $$
Publish $ n $ and $ e $, and you keep $ p, q, \Phi\br{n}, d $ secret. Let $ f\br{x} = x^e \mod n $ and $ g\br{x} = x^d \mod n $. Then
$$ \br{x^e}^d \equiv x^{de} \equiv x \mod n, $$
because $ de \equiv 1 \mod \Phi\br{n} $ and $ x^{\Phi\br{n}} \equiv 1 \mod n $. So if someone wants to send you a message $ c \in \ZZ / n\ZZ $, they compute $ c^e \in \ZZ / n\ZZ $, and send it to you. To decode it, you compute
$$ \br{c^e}^d \equiv c^{de} \equiv c \mod n. $$
This assumes that $ \br{c, n} = 1 $, but the probability of this is extremely high. The prevailing assumption is that with only the information $ n $ and $ e $, it is hopeless to discover $ d $, or to find any other way of recovering $ c $ from $ c^e $.

\lecture{9}{Wednesday}{24/10/18}

Lecture 9 is a problems class.

\subsection{Signing with RSA}

\lecture{10}{Friday}{26/10/18}

If you have functions $ f, g : \ZZ / n\ZZ \to \ZZ / n\ZZ $ with $ f \circ g = g \circ f = \id $, then you can also verify your identity, that is sign messages. Again, make $ f $ public, and any time you publish a message $ m $, you also publish $ g\br{m} $. Then anyone can apply $ f $ to $ g\br{m} $ to recover $ m = f\br{g\br{m}} $, but without $ g $, no one can forge your signature.

\subsection{Discrete logarithms}

Suppose that $ n $ is prime, or more generally that $ \unit{n} $ is cyclic. Let $ g $ be a generator for this group, that is a primitive root. For any $ a \in \unit{n} $, we can write $ a = g^m $ for some unique $ 0 \le m < \Phi\br{n} $. We call $ m $ the \textbf{discrete logarithm} of $ a $ to base $ g $, and write $ m = \log_g\br{a} $.

\begin{example*}
If you want to solve
$$ x^r \equiv a \mod n, $$
write $ x = g^y $, and the congruence becomes equivalent to
$$ yr \equiv \log_g\br{a} \mod \Phi\br{n}. $$
\end{example*}

Unfortunately, or fortunately for cryptography, computing $ \log_g $ is believed to be a hard problem. In particular, there is no known polynomial time algorithm.

\begin{example*}
Imagine that you have a system where you need to store passwords for different users, but you do not want to store the actual passwords. One way to do this is to choose a large prime $ p $ and a primitive root $ g $, and if someone inputs $ x $ as their password, you store $ g^x \mod p $. If they later input $ y $, you compute $ g^y $, and check it matches what you stored. If it does then $ y \equiv x \mod p - 1 $.
\end{example*}

\pagebreak

\section{Quadratic reciprocity}

\subsection{Quadratic residues}

Let $ p $ be a prime number.

\begin{definition}
If $ \br{a, p} = 1 $, then $ a $ is a \textbf{quadratic residue (QR)} if and only if there is a solution to $ x^2 \equiv a \mod p $. If $ \br{a, p} = 1 $ and is not a QR, it is called a \textbf{quadratic non-residue (QNR)}.
\end{definition}

\begin{example*}
\hfill
\begin{itemize}
\item If $ p = 2 $, $ 1 $ is a QR.
\item If $ p = 3 $, $ 1 $ is a QR, and $ -1 $ is a QNR, since $ 1^2 \equiv \br{-1}^2 \equiv 1 \mod 3 $.
\item If $ p = 5 $, $ 1 $ and $ 4 $ are QRs, and $ 2 $ and $ 3 $ are QNRs, since $ 1^2 \equiv 4^2 \equiv 1 \mod 5 $ and $ 2^2 \equiv 3^2 \equiv 4 \mod 5 $.
\end{itemize}
\end{example*}

\begin{lemma}
\label{lem:34}
If $ p > 2 $ then there are exactly $ \br{p - 1} / 2 $ QRs, and $ \br{p - 1} / 2 $ QNRs modulo $ p $.
\end{lemma}

\begin{proof}
The map
$$ \function{\unit{p}}{\unit{p}}{x}{x^2} $$
is a group homomorphism with kernel $ \cbr{\pm 1} $. So the image has order $ \br{p - 1} / 2 $, and the image is exactly the QRs.
\end{proof}

\begin{proposition}
\label{prop:35}
Suppose that $ \br{a, p} = \br{b, p} = 1 $. Then
\begin{itemize}
\item if $ a $ and $ b $ are both QRs, then $ ab $ is a QR,
\item if one of $ a $ and $ b $ is a QR and one is a QNR, then $ ab $ is a QNR, and
\item if $ a $ and $ b $ are both QNRs, then $ ab $ is a QR.
\end{itemize}
\end{proposition}

\begin{proof}
Let $ H $ be the image of
$$ \function{\unit{p}}{\unit{p}}{x}{x^2}, $$
that is $ H $ is the QRs. Then $ \unit{p} / H $ is a group of order two by Lemma \ref{lem:34}, so it is cyclic of order two. This statement is a restatement of Proposition \ref{prop:35}, since $ \unit{p} = H \cup 1 + H $.
\end{proof}

\begin{definition}
Let $ a \in \ZZ $ and $ p $ a prime. Then the \textbf{Legendre symbol} is
$$ \symbol{a}{p} =
\begin{cases}
1 & a \ \text{is a QR modulo} \ p \\
0 & p \mid a \\
-1 & a \ \text{is a QNR modulo} \ p
\end{cases}.
$$
\end{definition}

Proposition \ref{prop:35} can be restated as saying that
$$ \function{\unit{p}}{\cbr{\pm 1}}{a}{\symbol{a}{p}} $$
is a group homomorphism, that is
$$ \symbol{ab}{p} = \symbol{a}{p}\symbol{a}{p}. $$
Even holds if we do not assume that $ \br{a, p} = \br{b, p} = 1 $.

\lecture{11}{Tuesday}{30/10/18}

\begin{theorem}[Euler's criterion]
If $ p $ is an odd prime, and $ p \nmid a $, then
$$ \symbol{a}{p} \equiv a^{\tfrac{p - 1}{2}} \mod p. $$
\end{theorem}

\pagebreak

\begin{proof}
Let $ g $ be a primitive root modulo $ p $, and write $ a \equiv g^r \mod p $ for $ 0 \le r < p - 1 $. Now $ \br{g^{\br{p - 1} / 2}}^2 = g^{p - 1} \equiv 1 \mod p $. So $ g^{\br{p - 1} / 2} \equiv \pm 1 \mod p $. Since $ g $ is a primitive root, $ g^{\tfrac{p - 1}{2}} \not\equiv 1 \mod p $, so $ g^{\br{p - 1} / 2} \equiv -1 \mod p $. So
$$ a^{\tfrac{p - 1}{2}} \equiv \br{g^r}^{\tfrac{p - 1}{2}} \equiv \br{g^{\tfrac{p - 1}{2}}}^r \equiv \br{-1}^r \mod p. $$
But
\begin{align*}
\symbol{a}{p} = 1 \qquad
& \iff \qquad \exists s \in \ZZ, \ \br{g^s}^2 \equiv a \mod p \\
& \iff \qquad 2s \equiv r \mod p - 1 \\
& \iff \qquad r \in 2\ZZ \\
& \iff \qquad \br{-1}^r \equiv 1 \mod p.
\end{align*}
\end{proof}

\subsection{Computing Legendre symbols}

\begin{proposition}
$ -1 $ is a square modulo $ p $ if and only if $ p = 2 $ or $ p \equiv 1 \mod 4 $.
\end{proposition}

\begin{proof}
$ p = 2 $ is trivial. If $ p > 2 $, then by Euler's criterion,
$$ \symbol{-1}{p} \equiv \br{-1}^{\tfrac{p - 1}{2}} \mod p, $$
so in fact
$$ \symbol{-1}{p} = \br{-1}^{\tfrac{p - 1}{2}}. $$
Then
$$ \br{-1}^{\tfrac{p - 1}{2}} =
\begin{cases}
1 & p \equiv 1 \mod 4 \\
-1 & p \equiv 3 \mod 4
\end{cases}.
$$
\end{proof}

\begin{proposition}[Gauss' lemma]
$$ \symbol{2}{p} =
\begin{cases}
1 & p \equiv \pm 1 \mod 8 \\
-1 & p \equiv \pm 3 \mod 8
\end{cases},
$$
that is
$$ \symbol{2}{p} = \br{-1}^{\tfrac{p^2 - 1}{8}}. $$
\end{proposition}

\begin{proof}
$$ \symbol{2}{p} \equiv 2^{\tfrac{p - 1}{2}} \mod p, $$
by Euler's criterion. Let $ q = \br{p - 1} / 2 $, and let
$$ Q = \br{2}\br{4} \dots \br{p - 3}\br{p - 1} = \br{2\br{1}} \dots \br{2\br{q}} = 2^qq! = 2^{\tfrac{p - 1}{2}}q!. $$
Subtracting $ p $ from every term which is bigger than $ q $,
$$ Q \equiv \br{2}\br{4} \dots \br{-3}\br{-1} \equiv \br{-1}^rq! \mod p, $$
where $ r $ is the number of odd integers in $ 1, \dots, q $. Since $ p \nmid q! $, we have $ 2^{\br{p - 1} / 2} \equiv \br{-1}^r \mod p $. Now the following holds. \footnote{Exercise}
$$ \br{-1}^r =
\begin{cases}
1 & p \equiv \pm 1 \mod 8 \\
-1 & p \equiv \pm 3 \mod 8
\end{cases}.
$$
\end{proof}

\pagebreak

\begin{example*}
If $ p \equiv 1 \mod 8 $, say $ p = 1 + 8n $, then $ q = 4n $. Odd integers in $ 1, \dots, 4n $ are $ 1, 3, \dots, 4n - 3, 4n - 1 $, so $ r = 2n $.
\end{example*}

\begin{example*}
\hfill
\begin{itemize}
\item $ \symbol{2}{7} = 1 $, since $ 2 \equiv 3^2 \mod 7 $.
\item $ \symbol{2}{11} = -1 $, since squares modulo $ 11 $ are $ 1, 4, 9, 5, 3 $.
\item $ \symbol{-1}{11} = -1 $, so $ \symbol{-2}{11} = \symbol{2}{11}\symbol{-1}{11} = \br{-1}^2 = 1 $, since $ -2 \equiv 3^2 \mod 11 $.
\end{itemize}
\end{example*}

\begin{theorem}[Law of quadratic reciprocity]
\label{thm:40}
If $ p $ and $ q $ are odd primes, then
$$ \symbol{p}{q} = \symbol{q}{p}\br{-1}^{\br{\tfrac{p - 1}{2}}\br{\tfrac{q - 1}{2}}}, $$
that is $ \symbol{p}{q} = \symbol{q}{p} $ unless $ p \equiv q \equiv 3 \mod 4 $, when $ \symbol{p}{q} = -\symbol{q}{p} $.
\end{theorem}

\begin{example*}
\hfill
\begin{itemize}
\item $ \symbol{5}{p} = \symbol{p}{5} $ for $ p \ne 5 $. QRs modulo $ 5 $ are $ 1 $ and $ 4 $. So
$$ \symbol{5}{p} =
\begin{cases}
1 & p \equiv \pm 1 \mod 5 \\
-1 & p \equiv \pm 2 \mod 5
\end{cases}.
$$

\item What is $ \symbol{3}{p} $ for $ p \ne 3 $? If $ p \equiv 1 \mod 4 $, then
$$ \symbol{3}{p} = \symbol{p}{3} =
\begin{cases}
1 & p \equiv 1 \mod 3 \\
-1 & p \equiv -1 \mod 3
\end{cases}.
$$
If $ p \equiv -1 \mod 4 $, then
$$ \symbol{3}{p} = -\symbol{p}{3} =
\begin{cases}
1 & p \equiv -1 \mod 3 \\
-1 & p \equiv 1 \mod 3
\end{cases}.
$$
So
$$ \symbol{3}{p} =
\begin{cases}
1 & p \equiv \pm 1 \mod 12 \\
-1 & p \equiv \pm 5 \mod 12
\end{cases}.
$$
For example, $ \symbol{3}{7} = -1 $, since QRs are $ 1, 2, 4 $, and $ \symbol{3}{11} = 1 $, since $ 5^2 \equiv 3 \mod 11 $.
\item $ \symbol{6}{19} = \symbol{2}{19}\symbol{3}{19} = \br{-1}\br{-1} = 1 $, since $ \symbol{2}{19} = -1 $, because $ 19 \equiv 3 \mod 8 $, and $ \symbol{3}{19} \equiv -1 \mod 12 $, by the above.
\end{itemize}
\end{example*}

In general to compute $ \symbol{a}{p} $, we could do the following. Use that if $ a \equiv b \mod p $ then $ \symbol{a}{p} = \symbol{b}{p} $. So without loss of generality $ \abs{a} < p $. Then write $ a = \pm\prod_i q_i^{s_i} $ for $ q_i $ prime. Then
$$ \symbol{a}{p} = \symbol{\pm 1}{p} \prod_i \symbol{q_i}{p}^{s_i}. $$
If $ s_i $ is even, then $ \symbol{q_i}{p}^{s_i} = 1 $. If $ s_i $ is odd, then $ \symbol{q_i}{p}^{s_i} = \symbol{q_i}{p} $. We have formulas for $ \symbol{-1}{p} $ and $ \symbol{2}{p} $. If $ q $ is an odd prime, $ q < p $, then use quadratic reciprocity to relate $ \symbol{q}{p} $ and $ \symbol{p}{q} $. Then repeat modulo $ q $.

\pagebreak

\subsection{Proof of quadratic reciprocity}

\lecture{12}{Wednesday}{31/10/18}

The proof of this is due to Rousseau, in 1991. This resembles the proof we gave that $ \symbol{2}{p} = \br{-1}^{\br{p^2 - 1} / 8} $.

\begin{theorem}[Wilson's theorem]
If $ p $ is prime, then $ \br{p - 1}! \equiv -1 \mod p $.
\end{theorem}

\begin{proof}[Proof of Theorem \ref{thm:40}]
We will write down several choices of coset representatives for $ \cbr{\pm 1} $, and compare them, that is we will write down choices of $ x $ or $ -x $ for each $ x \in \unit{pq} $. Write elements of $ \unit{pq} $ as pairs $ \br{\alpha, \beta} \in \unit{p} \times \unit{q} $.
\begin{itemize}
\item For our first set of coset representatives, take
$$ \cbr{\br{x, y} \st 1 \le x \le \tfrac{p - 1}{2}, \ 1 \le y \le q - 1}. $$
Let $ A $ be the product of these coset representatives. This is by definition
$$ A = \br{\br{\br{\tfrac{p - 1}{2}}!}^{q - 1}, \br{-1}^{\tfrac{p - 1}{2}}}. $$
\item The second set of representatives is
$$ \cbr{\br{x, y} \st 1 \le x \le p - 1, \ 1 \le y \le \tfrac{q - 1}{2}}. $$
Let $ B $ be the product of these representatives. Then by symmetry,
$$ B = \br{\br{-1}^{\tfrac{q - 1}{2}}, \br{\br{\tfrac{q - 1}{2}}!}^{p - 1}}. $$
\item For the third set of representatives, select the pairs $ \br{x, y} $ which correspond via the Chinese remainder theorem to the set
$$ \cbr{1 \le i \le \tfrac{pq - 1}{2} \st \br{i, pq} = 1}. $$
Let $ C $ be the product of these coset representatives. What is the $ x $-coordinate of $ C $? It is
$$ \prod_{i = 1, \ \br{i, pq} = 1}^{\tfrac{pq - 1}{2}} i. $$
So
\begin{equation}
\label{eq:1}
\prod_{i = 1, \ \br{i, pq} = 1}^{\tfrac{pq - 1}{2}} i = \br{\prod_{i = 1, \ \br{i, p} = 1}^{\tfrac{pq - 1}{2}} i} \ \Bigg/ \ \br{\prod_{i = 1, \ \br{i, p} = 1, \ q \mid i}^{\tfrac{pq - 1}{2}} i},
\end{equation}
\begin{equation}
\label{eq:2}
\prod_{i = 1, \ \br{i, p} = 1}^{\tfrac{pq - 1}{2}} i = \br{\prod_{i = 1, \ \br{i, p} = 1}^{p\br{\tfrac{q - 1}{2}}} i}\br{\prod_{i = p\br{\tfrac{q - 1}{2}} + 1, \ \br{i, p} = 1}^{p\br{\tfrac{q - 1}{2}} + \tfrac{p - 1}{2}} i},
\end{equation}
\begin{equation}
\label{eq:3}
\prod_{i = 1, \ \br{i, p} = 1, \ q \mid i}^{\tfrac{pq - 1}{2}} i = \prod_{j = 1, \ \br{j, p} = 1}^{\tfrac{p - 1}{2}} qj = q^{\tfrac{p - 1}{2}}\br{\tfrac{p - 1}{2}}!.
\end{equation}
Combining $ \br{\ref{eq:1}}, \br{\ref{eq:2}}, \br{\ref{eq:3}} $, get that the $ x $-coordinate of the product is
$$ \prod_{i = 1, \ \br{i, pq} = 1}^{\tfrac{pq - 1}{2}} i = \dfrac{\br{p - 1}!^{\tfrac{q - 1}{2}}\br{\tfrac{p - 1}{2}}!}{q^{\tfrac{p - 1}{2}}\br{\tfrac{p - 1}{2}}!} = \dfrac{\br{-1}^{\tfrac{q - 1}{2}}}{q^{\tfrac{p - 1}{2}}}. $$
So $ C $, the product of these representatives, is
$$ C = \br{\br{-1}^{\tfrac{q - 1}{2}}\symbol{q}{p}, \br{-1}^{\tfrac{p - 1}{2}}\symbol{p}{q}}. $$
\end{itemize}

\pagebreak

$ A, B, C $ all agree up to sign, that is up to multiplication by $ \pm 1 $, that is up to multiplication by
$$ \br{-1, -1} \in \unit{p} \times \unit{q}. $$
Looking at $ y $-coordinates, $ C = \symbol{p}{q}A $. Similarly $ C = \symbol{q}{p}B $. So $ B = \symbol{q}{p}\symbol{p}{q}A $. To swap between $ A $ and $ B $, just change the signs of everything with $ 1 \le x \le \br{p - 1} / 2 $ and $ \br{q + 1} / 2 \le y \le q - 1 $. So
$$ B = \br{-1}^{\br{\tfrac{p - 1}{2}}\br{\tfrac{q - 1}{2}}}A. $$
So
$$ \symbol{q}{p}\symbol{p}{q} = \br{-1}^{\br{\tfrac{p - 1}{2}}\br{\tfrac{q - 1}{2}}}. $$
\end{proof}

\subsection{Jacobi symbols}

These are an extension of Legendre symbols which are useful for making computations.

\begin{definition}
Write $ b = \prod_i p_i^{r_i} $ for $ p_i $ distinct primes. Then the \textbf{Jacobi symbol} is
$$ \symbol{a}{b} = \prod_i \symbol{a}{p_i}^{r_i}. $$
\end{definition}

A warning is that $ \symbol{a}{b} = 1 $ does not imply that $ a $ is a square modulo $ b $. On the other hand, $ \symbol{a}{b} = -1 $ implies that $ a $ is not a square modulo $ b $.

\lecture{13}{Friday}{02/11/18}

\begin{lemma}
\hfill
\begin{enumerate}
\item $ \symbol{a_1a_2}{b} = \symbol{a_1}{b}\symbol{a_2}{b} $ and $ \symbol{a}{b_1b_2} = \symbol{a}{b_1}\symbol{a}{b_2} $.
\item $ \symbol{a}{b} $ depends only on $ a \mod b $.
\item $ \symbol{a^2}{b} = 1 $.
\item $ \symbol{-1}{b} = \br{-1}^{\br{b - 1} / 2} $.
\item $ \symbol{2}{b} = \br{-1}^{\br{b^2 - 1} / 8} $.
\item If $ a, b > 0 $ are both odd
$$ \symbol{a}{b}\symbol{b}{a} = \br{-1}^{\br{\tfrac{a - 1}{2}}\br{\tfrac{b - 1}{2}}}. $$
\end{enumerate}
\end{lemma}

\begin{proof}
All of these statements are true for Legendre symbols, that is for $ b $ prime, and $ a $ prime in $ 6 $. $ 1 $ to $ 3 $ follow immediately, and $ 4 $ to $ 6 $ also follows from $ 1 $ and the corresponding statements for Legendre symbols. For $ 5 $, it is enough to show that if it holds for $ b_1 $ and $ b_2 $, then it holds for $ b_1b_2 $. Since
$$ \symbol{2}{b_1b_2} = \symbol{2}{b_1}\symbol{2}{b_2}, $$
we need to show that
$$ \br{-1}^{\tfrac{b_1^2 - 1}{8}}\br{-1}^{\tfrac{b_2^2 - 1}{8}} = \br{-1}^{\tfrac{\br{b_1b_2}^2 - 1}{8}}, $$
that is need
$$ \br{b_1^2 - 1} + \br{b_2^2 - 1} \equiv \br{b_1b_2}^2 - 1 \mod 16, $$
that is $ \br{b_1^2 - 1}\br{b_2^2 - 1} \equiv 0 \mod 16 $. This is true because $ b_1^2 \equiv b_2^2 \equiv 1 \mod 4 $.
\end{proof}

\begin{example*}
Since
\begin{align*}
\symbol{7411}{9283}
& = -\symbol{9283}{7411} = -\symbol{1872}{7411} = -\symbol{16}{7411}\symbol{117}{7411} = -\symbol{117}{7411} = -\symbol{7411}{117} = -\symbol{40}{117} \\
& = -\symbol{8}{117}\symbol{5}{117} = -\symbol{2}{117}\symbol{5}{117} = \symbol{5}{117} = \symbol{117}{5} = \symbol{2}{5} = -1,
\end{align*}
$ 7411 $ is not a square modulo $ 9283 $.
\end{example*}

\pagebreak

\section{Sums of squares}

Which integers are the sum of two squares? Which integers are the sum of four squares?

\subsection{Sums of two squares}

\begin{definition}
We say that $ n \in \ZZ $ is a \textbf{sum of two squares} if
$$ n = x^2 + y^2, \qquad x, y \in \ZZ. $$
\end{definition}

\begin{example*}
If $ n = x^2 + y^2 $, then since $ x^2, y^2 \equiv 0, 1 \mod 4 $, we cannot have $ n \equiv 3 \mod 4 $.
\end{example*}

\begin{example*}
$ 21 \equiv 1 \mod 4 $, but $ 21 $ is not a sum of two squares. On the other hand, we will see that all primes which are $ 1 \mod 4 $ are sums of two squares.
\end{example*}

\begin{definition}
The \textbf{Gaussian integers} $ \ZZ\sbr{i} $ are the subring of $ \CC $ consisting of
$$ a + bi, \qquad a, b \in \ZZ. $$
\end{definition}

The \textbf{norm} is defined by
$$ \function[\N]{\ZZ\sbr{i}}{\ZZ_{> 0}}{a + bi}{a^2 + b^2}, $$
that is $ \N\br{z} = z\bar{z} $. Then $ \N\br{zw} = \br{zw}\br{\bar{zw}} = \br{z\bar{z}}\br{w\bar{w}} = \N\br{z}\N\br{w} $.

\begin{lemma}
\label{lem:46}
If $ m $ and $ n $ are each a sum of two squares, then so is $ mn $.
\end{lemma}

\begin{proof}
If $ z = a + bi $ and $ w = c + di $, then $ zw = \br{ac - bd} + \br{ad + bc}i $, so
$$ \br{a^2 + b^2}\br{c^2 + d^2} = \br{ac - bd}^2 + \br{ad + bc}^2. $$
\end{proof}

\begin{theorem}[Fermat's two square theorem]
\label{thm:47}
If $ p \equiv 1 \mod 4 $ is prime, then $ p $ is a sum of two squares.
\end{theorem}

Lemma \ref{lem:46} and Theorem \ref{thm:47} together allow you to give a complete classification of the integers which are sums of two squares, in terms of their prime factorisations.

\begin{definition}
A ring $ R $ is a \textbf{Euclidean domain} if it is an integral domain, that is $ ab = 0 $ implies that $ a = 0 $ or $ b = 0 $, and there exists a function $ \N : R \to \ZZ_{\ge 0} $ such that for all $ a, b \in R $ with $ b \ne 0 $, there exist $ q, r \in R $ such that $ a = qb + r $, and $ r = 0 $ or $ \N\br{r} < \N\br{b} $.
\end{definition}

If $ R $ is a Euclidean domain, then you can carry out Euclid's algorithm. In particular, irreducible elements are the same as prime elements, and every element can be factored as a product of primes, uniquely up to reordering and multiplication by units. Then $ \ZZ\sbr{i} $ together with $ \N $ is a Euclidean domain. By definition, $ n \in \ZZ $ is a sum of two squares if and only if there exists $ z \in \ZZ\sbr{i} $ with $ \N\br{z} = n $. Since $ \N\br{zw} = \N\br{z}\N\br{w} $, all we have to do is to figure out what the primes in $ \ZZ\sbr{i} $ are, and what their norms are. The units in $ \ZZ\sbr{i} $ are $ \pm 1 $ and $ \pm i $. \footnote{Exercise} Two elements of $ \ZZ\sbr{i} $ are \textbf{associates} if their ratio is a unit, that is $ z $ and $ w $ are associates if $ z = uw $ for $ u = \pm 1, \pm i $.

\lecture{14}{Tuesday}{06/11/18}

\begin{lemma}
Let $ p $ be a prime in $ \ZZ\sbr{i} $. Then there is a prime $ q $ of $ \ZZ $ such that either $ \N\br{p} = q $ or $ \N\br{p} = q^2 $. In the latter case, $ p $ is an associate of $ q $. Given $ q $ a prime in $ \ZZ $, there exists $ p $ such that $ \N\br{p} = q $ if and only if $ q $ is a sum of two squares.
\end{lemma}

\begin{proof}
Write $ n = \N\br{p} $, and let $ n = q_1^{s_1} \dots q_r^{s_r} $ be the prime factorisation of $ n $ in $ \ZZ $. By definition $ n = p\bar{p} $, so $ p \mid n $ in $ \ZZ\sbr{i} $, and so since $ p $ is prime, $ p \mid q_i $ for some $ i $. Write $ q = q_i $. Then $ p \mid q $ implies that $ q = pv $ for some $ v $, so $ \N\br{p}\N\br{v} = \N\br{pv} = \N\br{q} = q^2 $. If $ \N\br{p} = 1 $, then $ p $ is a unit, a contradiction. So $ \N\br{p} \mid q^2 $, so $ \N\br{p} = q $ or $ \N\br{p} = q^2 $, as claimed. If $ \N\br{p} = q^2 $, then $ \N\br{v} = 1 $, so $ v $ is a unit, and since $ q = pv $, $ p $ is an associate of $ q $, by definition. If $ \N\br{p} = q $, then writing $ p = a + bi $, we have $ q = a^2 + b^2 $. Conversely, if $ q = a^2 + b^2 = \br{a + bi}\br{a - bi} $,
then since $ p \mid q $, we have either $ p \mid a + bi $ or $ p \mid a - bi $, so $ \N\br{p} \mid \N\br{a + bi} = q $ or $ \N\br{p} \mid \N\br{a - bi} = q $, and either way $ \N\br{p} = q $.
\end{proof}

\pagebreak

\begin{corollary}
\label{cor:50}
The primes in $ \ZZ\sbr{i} $ are either of the form $ a + bi $ with $ a^2 + b^2 $ a prime in $ \ZZ $, or are primes of $ \ZZ $ which are not sums of two squares.
\end{corollary}

\begin{theorem}
If $ p = 2 $ or $ p \equiv 1 \mod 4 $, then $ p $ is a sum of two squares.
\end{theorem}

\begin{proof}
By Corollary \ref{cor:50}, we just have to show that $ p $ is not a prime in $ \ZZ\sbr{i} $. There exists $ n $ such that $ n^2 \equiv -1 \mod p $. If $ p = 2 $ obvious, and if $ p \equiv 1 \mod 4 $,
$$ \symbol{-1}{p} = \br{-1}^{\tfrac{p - 1}{2}} = 1, $$
by Euler's criterion. That is, $ p \mid n^2 + 1 = \br{n + i}\br{n - i} $. If $ p $ were prime, then $ p \mid n + i $ or $ p \mid n - i $, that is there exist $ c, d \in \ZZ $ such that $ n \pm i = p\br{c \pm di} $, so $ 1 = pd $, a contradiction.
\end{proof}

\begin{remark*}
If $ p \equiv 3 \mod 4 $ then $ p $ is not a sum of two squares, even modulo four.
\end{remark*}

\begin{remark*}
In practice, to go from $ n^2 + 1 \equiv 0 \mod p $ to finding $ a $ and $ b $ with $ a^2 + b^2 = p $, you just compute $ \br{n + i, p} = a + bi $. You can do this computation with Euclid's algorithm in $ \ZZ\sbr{i} $.
\end{remark*}

\begin{theorem}
$ n \in \ZZ $ is a sum of two squares if and only if its prime factorisation only contains primes congruent to $ 3 \mod 4 $ to even powers, that is
$$ n = 2^a\prod_{p_i \equiv 1 \mod 4} p_i^{r_i}\prod_{q_i \equiv 3 \mod 4} q_i^{2s_i}. $$
\end{theorem}

\begin{proof}
Suppose $ n $ is of this form. Then $ 2 $, each $ p_i $, and each $ q_i^2 $ are all sums of two squares, so $ n $ is a sum of two squares by Lemma \ref{lem:46}. Conversely suppose that $ n = a^2 + b^2 $, and write $ a + bi $ as a product of primes in $ \ZZ\sbr{i} $. Then $ n = \N\br{a + bi} $ is the product of the norms of these primes, and we already saw that the norms of primes in $ \ZZ\sbr{i} $ are either $ 2 $, a prime which is $ 1 \mod 4 $, or the square of a prime which is $ 3 \mod 4 $.
\end{proof}

\subsection{Sums of four squares - the ring of quaternions}

Lagrange's theorem states that every positive integer is a sum of four squares.

\begin{definition}
$ \HH $, the \textbf{ring of quaternions}, is the ring of sums
$$ a + bi + cj + dk, \qquad a, b, c, d \in \RR, $$
such that
\begin{itemize}
\item addition is
$$ \br{a + bi + cj + dk} + \br{A + Bi + Cj + Dk} = \br{a + A} + \br{b + B}i + \br{c + C}j + \br{d + D}k, $$
\item multiplication is
$$ ij = -ji = k, \qquad jk = -kj = i, \qquad ki = -ik = j. $$
\end{itemize}
If $ z = a + bi + cj + dk $, we write $ z^* = a - bi - cj - dk $, so $ \br{zw}^* = w^*z^* $.
\end{definition}

Define
$$ \N\br{z} = zz^* = a^2 + b^2 + c^2 + d^2. $$
Then $ \N\br{zw} = zw\br{zw}^* = zww^*z^* = z\N\br{w}z^* = zz^*\N\br{w} = \N\br{z}\N\br{w} $, because $ \N\br{w} \in \RR $. So
\begin{align*}
\br{a^2 + b^2 + c^2 + d^2}\br{x^2 + y^2 + z^2 + w^2}
= \ & \N\br{a + bi + cj + dk}\N\br{x + yi + zj + wk} \\
= \ & \N\br{\br{a + bi + cj + dk}\br{x + yi + zj + wk}} \\
= \ & \br{ax - by - cz - dw}^2 + \br{ay + bx + cw - dz}^2 \\
+ & \br{az - bw + cx + dy}^2 + \br{aw + bz - cy + dx}^2.
\end{align*}
In particular, if $ m $ and $ n $ are sums of four squares, then $ mn $ is a sum of four squares. So to prove Lagrange's theorem, it suffices to show that all primes are sums of four squares.

\pagebreak

\subsection{Proof of Lagrange's theorem}

We already saw that $ 2 $, and any prime congruent to $ 1 \mod 4 $, is a sum of two squares. It remains to show that any prime congruent to $ 3 \mod 4 $ is a sum of four squares.

\lecture{15}{Wednesday}{07/11/18}

\begin{lemma}
\label{lem:54}
If $ p \equiv 3 \mod 4 $ is prime, then there exist $ x $ and $ y $ such that
$$ x^2 + y^2 + 1 \equiv 0 \mod p. $$
\end{lemma}

\begin{proof}
Firstly, claim there exists $ a $ such that $ \symbol{a}{p} = 1 $ and $ \symbol{a + 1}{p} = -1 $. If not, since $ \symbol{1}{p} = 1 $, we must have
$$ \symbol{2}{p} = \dots = \symbol{p - 1}{p} = 1. $$
But we know that there are $ \br{p - 1} / 2 $ values of $ b $ with $ 1 \le b \le p - 1 $ and $ \symbol{b}{p} = -1 $, a contradiction. Since $ p \equiv 3 \mod 4 $, $ \symbol{-1}{p} = -1 $ by Euler's criterion. So
$$ \symbol{-\br{a + 1}}{p} = \symbol{a + 1}{p}\symbol{-1}{p} = 1. $$
Choose $ x $ and $ y $ such that
$$ x^2 \equiv a \mod p, \qquad y^2 \equiv -\br{a + 1} \mod p. $$
Then $ x^2 + y^2 \equiv -1 \mod p $.
\end{proof}

By Lemma \ref{lem:54}, there exist $ x, y \in \ZZ $ such that
$$ x^2 + y^2 + 1 = pr, $$
for some $ r $. Since the congruence $ x^2 + y^2 + 1 \equiv 0 \mod p $ only depends on $ x $ and $ y $ modulo $ p $, we can find $ x $ and $ y $ with $ -p / 2 < x, y < p / 2 $. Then
$$ \dfrac{x^2 + y^2 + 1}{p} = r < p. $$

\begin{proposition}
\label{prop:55}
Suppose that
$$ x^2 + y^2 + z^2 + w^2 = pr, \qquad 1 \le r < p. $$
If $ r > 1 $, there exist $ x', y', z', w', r' $ such that
$$ x'^2 + y'^2 + z'^2 + w'^2 = pr', \qquad 1 \le r' < r. $$
\end{proposition}

Proposition \ref{prop:55} implies that $ p $ is a sum of four squares, starting with $ x, y, r $ as above, $ z = 1 $, and $ w = 0 $.

\begin{proof}
\hfill
\begin{itemize}
\item Suppose firstly that $ r $ is even. Then either $ x, y, z, w $ are all even, all odd, or two are even and two are odd. So without loss of generality $ x \equiv y \mod 2 $ and $ z \equiv w \mod 2 $. Then take
$$ x' = \dfrac{x + y}{2}, \qquad y' = \dfrac{x - y}{2}, \qquad z' = \dfrac{z + w}{2}, \qquad w' = \dfrac{z - w}{2}, \qquad r' = \dfrac{r}{2}. $$

\pagebreak

\item Suppose now that $ r $ is odd, and choose $ a, b, c, d \in \br{-r / 2, r / 2} $ such that
$$ x \equiv a \mod r, \qquad y \equiv b \mod r, \qquad z \equiv c \mod r, \qquad w \equiv d \mod r. $$
Then
$$ a^2 + b^2 + c^2 + d^2 \equiv x^2 + y^2 + z^2 + w^2 = pr \equiv 0 \mod r. $$
Write $ a^2 + b^2 + c^2 + d^2 = rr' $. Then $ rr' < 4\br{r / 2}^2 = r^2 $, so $ 0 \le r' < r $. If $ r' = 0 $ then $ a = b = c = d = 0 $, so $ r' $ divides each of $ x, y, z, w $. Since $ x^2 + y^2 + z^2 + w^2 = pr $, we get $ r^2 \mid pr $ so $ r \mid p $, and since $ r < p $, we get $ r = 1 $, and we are done. Otherwise $ 1 \le r' < r $. Then
\begin{align*}
\br{rr'}\br{rp}
= \ & \br{a^2 + b^2 + c^2 + d^2}\br{x^2 + y^2 + z^2 + w^2} \\
= \ & \br{ax + by + cz + dw}^2 + \br{-ay + bx + cw - dz}^2 \\
+ & \br{-az - bw + cx + dy}^2 + \br{-aw + bz - cy + dx}^2.
\end{align*}
Then
\begin{align*}
ax + by + cz + dw \equiv x^2 + y^2 + z^2 + w^2 & \equiv 0 \mod r, \\
-ay + bx + cw - dz \equiv -xy + yx + zw - wz & \equiv 0 \mod r, \\
-az - bw + cx + dy \equiv -xz - yw + zx + wy & \equiv 0 \mod r, \\
-aw + bz - cy + dx \equiv -xw + yz - zy + wx & \equiv 0 \mod r.
\end{align*}
So take
$$ x' = \dfrac{ax + by + cz + dw}{r}, \qquad y' = \dfrac{-ay + bx + cw - dz}{r}, $$
$$ z' = \dfrac{-az - bw + cx + dy}{r}, \qquad w' = \dfrac{-aw + bz - cy + dx}{r}. $$
\end{itemize}
\end{proof}

\begin{remark}
This can be interpreted as a version of Euclid's algorithm in the ring
$$ \cbr{\dfrac{a + bi + cj + dk}{2} \st a \equiv b \equiv c \equiv d \mod 2}. $$
\end{remark}

\begin{note*}
This ring is non-commutative, and also, for example, $ 5 = \br{1 - 2i}\br{1 - 2i} = \br{1 + 2j}\br{1 - 2j} $, so you have to be careful with unique factorisation, etc.
\end{note*}

\subsection{Sums of three squares}

$ 7 $ is the smallest positive integer which is not a sum of three squares. In fact no integer congruent to $ 7 \mod 8 $ can be a sum of three squares, because the squares modulo $ 8 $ are $ 0, 1, 4 $.

\begin{theorem}
A positive integer is not a sum of three squares if and only if it is of the form
$$ 4^a\br{8k + 7}. $$
\end{theorem}

Proving that numbers are not of this form is beyond this course. Serre's a course in arithmetic is a good place to look.

\pagebreak

\section{Pell's equation}

\subsection{Pell's equation}

Let $ d \in \ZZ_{> 1} $ be squarefree. \textbf{Pell's equation} is
$$ x^2 - dy^2 = 1. $$

\begin{example*}
Let $ d = 2 $. Then $ \br{x, y} = \br{3, 2} $ is a solution. In fact, there are infinitely many solutions, and this is true for any $ d $.
\end{example*}

We will find it useful to write
$$ x^2 - dy^2 = \br{x + \sqrt{d}y}\br{x - \sqrt{d}y}. $$
This suggests that we should look at a ring like
$$ \ZZ\sbr{\sqrt{d}} = \cbr{a + b\sqrt{d} \st a, b \in \ZZ}. $$

\begin{definition}
If $ \alpha \in \CC $, then $ \ZZ\sbr{\alpha} $ is the \textbf{smallest subring of $ \CC $ containing $ \alpha $}.
\end{definition}

\begin{example*}
\hfill
\begin{itemize}
\item If $ \alpha = 1 $, then $ \ZZ\sbr{\alpha} = \ZZ $.
\item If $ \alpha = i $, $ \ZZ\sbr{i} $ is what we wrote before.
\item On the other hand $ \ZZ\sbr{\pi} $ is the ring of $ a_0 + \dots + a_n\pi^n $ for $ a_i \in \ZZ $ and $ n $ arbitrary.
\item Also $ \ZZ\sbr{\sqrt[3]{2}} $ is not just the set $ \cbr{a + b\sqrt[3]{2} \st a, b \in \ZZ} $, because this set does not contain $ \br{\sqrt[3]{2}}^2 = \sqrt[3]{4} $.
\item Also $ \ZZ\sbr{\tfrac{1}{p}} $ contains $ 1 / p^n $ for all $ n $, so in fact $ \ZZ\sbr{\tfrac{1}{p}} = \cbr{a / p^n \st a \in \ZZ, \ n \ge 0} $.
\end{itemize}
\end{example*}

An alternative definition is that $ \ZZ\sbr{\alpha} $ is the intersection of all subrings of $ \CC $ containing $ \alpha $.

\lecture{16}{Friday}{09/11/18}

Lecture 16 is a problems class.

\subsection{Quadratic subrings of \texorpdfstring{$ \CC $}{C}}

\lecture{17}{Tuesday}{13/11/18}

\begin{definition}
Say that $ \alpha \in \CC $ is an \textbf{algebraic integer of degree two} if it is a root of a polynomial
$$ X^2 + aX + b, \qquad a, b \in \ZZ, \qquad \alpha \notin \ZZ. $$
\end{definition}

\begin{example*}
\hfill
\begin{itemize}
\item $ \alpha = i $ is a root of $ X^2 + 1 $.
\item $ \alpha = \sqrt{d} $ is a root of $ X^2 - d $ for $ d > 1 $ squarefree.
\end{itemize}
\end{example*}

\begin{proposition}
If $ \alpha $ is an algebraic integer of degree two, then
$$ \ZZ\sbr{\alpha} = \cbr{x + y\alpha \st x, y \in \ZZ}. $$
\end{proposition}

\begin{proof}
Since $ \alpha \notin \ZZ $, we have $ \alpha \notin \QQ $, since if $ \alpha = r / s $ for $ \br{r, s} = 1 $ then $ r^2 + ars + bs^2 = 0 $,
so $ s \mid r^2 $, so $ s \mid 1 $, so $ \alpha \in \ZZ $. So if $ x, y \in \ZZ $ and $ x + y\alpha = 0 $, then $ x = y = 0 $. Certainly every $ x + y\alpha \in \ZZ\sbr{\alpha} $. The set $ \cbr{x + y\alpha} $ is closed under addition and subtraction, so we only have to check that is closed under multiplication. But
\begin{align*}
\br{x + y\alpha}\br{X + Y\alpha}
& = xX + \br{xY + yX}\alpha + yY\alpha^2 \\
& = xX + \br{xY + yX}\alpha + yY\br{a\alpha + b} \\
& = \br{xX + byY} + \br{xY + yX + ayY}\alpha.
\end{align*}
\end{proof}

\pagebreak

If $ \alpha $ is an algebraic integer of degree two, say that $ \ZZ\sbr{\alpha} $ is a \textbf{real quadratic subring} of $ \CC $ if $ \alpha \in \RR $, and an \textbf{imaginary quadratic subring} of $ \CC $ if $ \alpha \notin \RR $. Let $ \alpha^* $ be the other root of $ X^2 + aX + b = 0 $.

\begin{example*}
$ i^* = -i = \bar{i} $ and $ \sqrt{d}^* = -\sqrt{d} $.
\end{example*}

If $ z = x + y\alpha \in \ZZ\sbr{\alpha} $, write $ z^* = x + y\alpha^* $. If $ \ZZ\sbr{\alpha} $ is imaginary quadratic, then $ \alpha^* = \bar{\alpha} $, and $ z^* = \bar{z} $. This is not true if $ \ZZ\sbr{\alpha} $ is real quadratic. Define $ \N\br{z} = zz^* $. Since $ \alpha $ and $ \alpha^* $ are the roots of $ X^2 + aX + b $, we have $ \alpha + \alpha^* = -a $ and $ \alpha\alpha^* = b $. If $ z = x + y\alpha $, then
$$ \N\br{z} = \br{x + y\alpha}\br{x + y\alpha^*} = x^2 + xy\br{\alpha + \alpha^*} + y^2\alpha\alpha^* = x^2 - axy + by^2 \in \ZZ. $$
We have $ \br{zw}^* = z^*w^* $, so $ \N\br{z}\N\br{w} = zz^*ww^* = \br{zw}\br{zw}^* = \N\br{zw} $. So $ \N : \ZZ\sbr{\alpha} \to \ZZ $ is multiplicative. Then $ \N\br{x + y\alpha} = 0 $ if and only if $ x = y = 0 $. \footnote{Exercise} If $ \ZZ\sbr{\alpha} $ is imaginary quadratic then $ z^* = \bar{z} $, and $ \N\br{z} \ge 0 $. If $ \ZZ\sbr{\alpha} $ is real quadratic, we can have $ \N\br{z} < 0 $.

\begin{example*}
If $ \alpha = \sqrt{d} $, then $ \N\br{\sqrt{d}} = \br{\sqrt{d}}\br{-\sqrt{d}} = -d < 0 $, and
$$ \N\br{x + y\sqrt{d}} = \br{x + y\sqrt{d}}\br{x + y\sqrt{d}}^* = \br{x + y\sqrt{d}}\br{x - y\sqrt{d}} = x^2 - dy^2. $$
So solutions to Pell's equation are the same thing as elements of $ \ZZ\sbr{\alpha} $ of norm one.
\end{example*}

\subsection{Factorisation in quadratic rings}

\begin{definition}
The \textbf{units} of $ \ZZ\sbr{\alpha} $ are by definition the elements with multiplicative inverses, and they form a group $ \ZZ\sbr{\alpha}^\times $ under multiplication. We say that $ z, w \in \ZZ\sbr{\alpha} $ are \textbf{associates} if $ z = uw $ for $ u \in \ZZ\sbr{\alpha}^\times $.
\end{definition}

If $ u \in \ZZ\sbr{\alpha}^\times $, then write $ 1 = uv $. Then $ 1 = \N\br{1} = \N\br{u}\N\br{v} $, so $ \N\br{u} = \pm 1 $. Conversely if $ \N\br{u} = \pm 1 $, then $ \pm 1 = \N\br{u} = u\br{u^*} $, so $ u\br{\pm u^*} = 1 $, so $ u \in \ZZ\sbr{\alpha}^\times $. So
$$ \ZZ\sbr{\alpha}^\times = \cbr{z \in \ZZ\sbr{\alpha} \st \N\br{z} = \pm 1}. $$
Write
$$ \ZZ\sbr{\alpha}^{\times, 1} = \cbr{z \in \ZZ\sbr{\alpha} \st \N\br{z} = 1}. $$
Then $ \ZZ\sbr{\alpha}^{\times, 1} $ is a multiplicative subgroup of $ \ZZ\sbr{\alpha}^\times $.

\subsection{Back to Pell's equation}

\begin{example*}
If $ \alpha = \sqrt{d} $ for $ d > 1 $ squarefree, then
$$ \ZZ\sbr{\sqrt{d}}^{\times, 1} = \cbr{x + y\sqrt{d} \st x^2 - dy^2 = 1}. $$
\end{example*}

If $ \ZZ\sbr{\alpha} $ is imaginary quadratic, then $ \ZZ\sbr{\alpha}^\times = \ZZ\sbr{\alpha}^{\times, 1} $ is finite. What are the possibilities for this group? \footnote{Exercise} What is $ \ZZ\sbr{\sqrt{d}}^{\times, 1} $? Certainly contains $ \pm 1 $. Anything else will be of the form $ x + y\sqrt{d} $ with $ x, y \ne 0 $.

\begin{lemma}
\label{lem:62}
Let $ x + y\sqrt{d} $ be an element of $ \ZZ\sbr{\sqrt{d}}^{\times, 1} $. Then
\begin{align*}
x > 0, \qquad y > 0 \qquad & \iff \qquad x + y\sqrt{d} > 1, \\
x > 0, \qquad y < 0 \qquad & \iff \qquad 0 < x + y\sqrt{d} < 1, \\
x < 0, \qquad y > 0 \qquad & \iff \qquad -1 < x + y\sqrt{d} < 0, \\
x < 0, \qquad y < 0 \qquad & \iff \qquad x + y\sqrt{d} < -1.
\end{align*}
\end{lemma}

\begin{proof}
If $ x, y > 0 $ then $ x + y\sqrt{d} > y\sqrt{d} \ge \sqrt{d} > 1 $. Then $ x - y\sqrt{d} = 1 / \br{x + y\sqrt{d}} \in \br{0, 1} $. So replacing $ y $ by $ -y $, we get $ x > 0 $ and $ y < 0 $, so $ 0 < x + y\sqrt{d} < 1 $. Replacing $ \br{x, y} $ with $ \br{-x, -y} $ gives the forward in the third and fourth lines. Since the four possibilities for the right hand side are exhaustive for $ x, y \ne 0 $, we are done.
\end{proof}

\pagebreak

\begin{lemma}
\label{lem:63}
Let $ z = x + y\sqrt{d} $ and $ z' = x' + y'\sqrt{d} $ be two elements of $ \ZZ\sbr{\sqrt{d}}^{\times, 1} $ with $ z, z' > 1 $, that is $ x, y, x', y' > 0 $. Then $ z > z' $ if and only if $ y > y' $.
\end{lemma}

\begin{proof}
$ z - 1 / z = x + y\sqrt{d} - \br{x - y\sqrt{d}} = 2y\sqrt{d} $, so just need to check that $ z > z' $ if and only if $ z - 1 / z > z' - 1 / z' $. But $ z - 1 / z $ is increasing, since its derivative is $ 1 + 1 / z^2 > 0 $.
\end{proof}

\lecture{18}{Wednesday}{14/11/18}

Suppose that there exists $ z \in \ZZ\sbr{\sqrt{d}}^{\times, 1} $, so $ z \ne \pm 1 $. By replacing $ z $ by $ \pm z^{\pm 1} $, we can assume that $ z > 1 $. So by Lemma \ref{lem:62}, if $ z = x + y\sqrt{d} $, then $ x, y > 0 $. Let
$$ \epsilon = x + y\sqrt{d} \in \ZZ\sbr{\sqrt{d}}^{\times, 1}, \qquad x, y > 0, $$
with $ y $ as small as possible. Call $ \epsilon $ the \textbf{fundamental $ 1 $-unit} of $ \ZZ\sbr{\sqrt{d}} $.

\begin{proposition}
Suppose that $ \ZZ\sbr{\sqrt{d}}^{\times, 1} \ne \cbr{\pm 1} $, and let $ \epsilon $ be the fundamental $ 1 $-unit. Then every element of $ \ZZ\sbr{\sqrt{d}}^{\times, 1} $ is of the form $ \pm\epsilon^n $ for some $ n \in \ZZ $. Conversely, $ \N\br{\pm\epsilon^n} = \N\br{\pm 1}\N\br{\epsilon}^n = 1 $.
\end{proposition}

\begin{proof}
Let $ z \in \ZZ\sbr{\sqrt{d}}^{\times, 1} $, so $ z \ne \pm 1 $. After replacing $ z $ by $ \pm z^{\pm 1} $, we may assume that $ z > 1 $. Choose $ n \ge 0 $ such that $ \epsilon^n \le z < \epsilon^{n + 1} $. Then $ 1 \le z\epsilon^{-n} < \epsilon $, and $ \N\br{z\epsilon^{-n}} = \N\br{z}\N\br{\epsilon}^{-n} = 1 $. So $ z\epsilon^{-n} \in \ZZ\sbr{\sqrt{d}}^{\times, 1} $. So by the choice of $ \epsilon $, and Lemma \ref{lem:63}, we have $ z\epsilon^{-n} = 1 $, that is $ z = \epsilon^n $.
\end{proof}

\begin{example*}
Let $ d = 2 $ and $ x^2 - 2y^2 = 1 $. Then $ y = 2 $ and $ x = 3 $ is a solution. So $ \epsilon = 3 + 2\sqrt{2} $. Then $ \epsilon^2 = \br{3 + 2\sqrt{2}}^2 = 17 + 12\sqrt{2} $, and $ 17^2 - 2\br{12}^2 = 1 $.
\end{example*}

\subsection{Constructing the fundamental \texorpdfstring{$ 1 $}{1}-unit}

The idea is that if $ x^2 - dy^2 = 1 $ for $ x, y > 0 $, then $ x / y \approx \sqrt{d} $. Then $ \abs{x - y\sqrt{d}} = 1 / \abs{x + y\sqrt{d}} $, which is small. So one way to try to find $ 1 $-units is to find rational numbers which are good approximations to $ \sqrt{d} $. Want to make $ \abs{x / y - \sqrt{d}} $ as small as possible for $ y $ of a given size. More generally, if $ \alpha \in \RR \setminus \QQ $, we might want to find $ x, y > 0 $ such that
$$ \abs{\dfrac{x}{y} - \alpha} < \dfrac{C}{y^n}, $$
where $ C $ and $ n $ are fixed.
\begin{itemize}[leftmargin=1in]
\item[$ n = 0 $.] Trivial.
\item[$ n = 1 $, $ C = 1 $.] Trivial, by just choosing any $ y $ and $ x / y $ as close to $ \alpha $ as you can.
\item[$ n = 2 $, $ C = 1 $.] Not obvious. In fact there always exist infinitely many $ x $ and $ y $ with $ \abs{x / y - \alpha} < 1 / y^2 $, as we now show.
\end{itemize}

\begin{theorem}[Dirichlet's theorem]
\label{thm:65}
Let $ \alpha \in \RR \setminus \QQ $, and let $ Q \in \ZZ_{> 1} $. Then there exist $ p, q \in \ZZ $, such that
$$ 1 \le q < Q, \qquad \abs{p - q\alpha} < \dfrac{1}{Q}. $$
\end{theorem}

\begin{proof}
For $ 1 \le k \le Q - 1 $, let $ a_k = \fbr{k\alpha} $. Then $ 0 < k\alpha - a_k < 1 $. Consider the $ Q $ intervals
$$ \sbr{0, \dfrac{1}{Q}}, \qquad \dots, \qquad \sbr{\dfrac{Q - 1}{Q}, 1}. $$
The set
$$ \cbr{0, \alpha - a_1, \dots, \br{Q - 1}\alpha - a_{Q - 1}, 1}, $$
contains $ Q + 1 $ elements, so some pair of them must be in the same interval. The difference of these two elements is of the form $ p - q\alpha $ for $ 1 \le q < Q $.
\end{proof}

\pagebreak

\begin{corollary}
\label{cor:66}
For any $ \alpha \in \RR \setminus \QQ $, there exist infinitely many pairs $ p, q \in \ZZ $ such that
$$ \abs{\alpha - \dfrac{p}{q}} < \dfrac{1}{q^2}. $$
\end{corollary}

\begin{proof}
Certainly there exists $ p $ for $ q = 1 $. It is then enough to prove that if $ \abs{\alpha - p / q} < 1 / q^2 $, there exist $ p' $ and $ q' $ such that
$$ \abs{\alpha - \dfrac{p'}{q'}} < \dfrac{1}{\br{q'}^2}, \qquad \abs{\alpha - \dfrac{p'}{q'}} < \abs{\alpha - \dfrac{p}{q}}. $$
Choose $ Q $ such that $ 1 / Q < \abs{\alpha - p / q} $. By Theorem \ref{thm:65}, there exist $ p' $ and $ q' $ with
$$ 1 \le q' < Q, \qquad \abs{\alpha - \dfrac{p'}{q'}} < \dfrac{1}{Qq'} < \dfrac{1}{\br{q'}^2}. $$
Also
$$ \abs{\alpha - \dfrac{p'}{q'}} < \dfrac{1}{Qq'} \le \dfrac{1}{Q} < \abs{\alpha - \dfrac{p}{q}}, $$
as required.
\end{proof}

We can now show the following.

\begin{theorem}
If $ d > 1 $ is squarefree, then there exist $ x $ and $ y $ such that $ y \ne 0 $ and $ x^2 - dy^2 = 1 $.
\end{theorem}

\begin{proof}
By Corollary \ref{cor:66}, there exist infinitely many $ \br{p_i, q_i} $ for $ p_i, q_i > 0 $ such that $ \abs{p_i / q_i - \sqrt{d}} < 1 / q_i^2 $, that is $ \abs{p_i - q_i\sqrt{d}} < 1 / q_i $. Then
$$ \abs{p_i + q_i\sqrt{d}} \le \abs{p_i - q_i\sqrt{d}} + 2q_i\sqrt{d} < \dfrac{1}{q_i} + 2q_i\sqrt{d} < 3q_i\sqrt{d}. $$
So
$$ \abs{\N\br{p_i + q_i\sqrt{d}}} = \abs{p_i + q_i\sqrt{d}}\abs{p_i - q_i\sqrt{d}} < 3q_i\sqrt{d}\br{\dfrac{1}{q_i}} = 3\sqrt{d}. $$
So there exists $ M \in \br{-3\sqrt{d}, 3\sqrt{d}} $ such that $ \N\br{p_i + q_i\sqrt{d}} = M $ for infinitely many $ i $. Then there exists $ \br{p_0, q_0} $ such that
$$ p_i \equiv p_0 \mod M, \qquad q_i \equiv q_0 \mod M, $$
for infinitely many $ i $. Now consider $ \br{p_i, q_i} \ne \br{p_j, q_j} $ of this form, that is
$$ \N\br{p_i + q_i\sqrt{d}} = \N\br{p_j + q_j\sqrt{d}} = M, \qquad p_i \equiv p_j \mod M, \qquad q_i \equiv q_j \mod M. $$
Then
$$ \dfrac{p_i - q_i\sqrt{d}}{p_j - q_j\sqrt{d}} = \dfrac{\br{p_i - q_i\sqrt{d}}\br{p_j + q_j\sqrt{d}}}{M} = \dfrac{\br{p_ip_j - dq_iq_j} + \br{p_iq_j - p_jq_i}\sqrt{d}}{M}, $$
$$ p_iq_j \equiv p_jq_i \mod M, \qquad p_ip_j - dq_iq_j \equiv p_i^2 - dq_i^2 = M \equiv 0 \mod M. $$
So
$$ \N\br{\dfrac{p_i - q_i\sqrt{d}}{p_j - q_j\sqrt{d}}} = \dfrac{M}{M} = 1, $$
so $ \br{p_i - q_i\sqrt{d}} / \br{p_j - q_j\sqrt{d}} \in \ZZ\sbr{\sqrt{d}}^{\times, 1} $, as required.
\end{proof}

\subsection{The equation \texorpdfstring{$ x^2 - dy^2 = - 1 $}{x2 - dy2 = -1}}

\lecture{19}{Friday}{16/11/18}

$ x^2 - dy^2 = -1 $ has a solution if and only if there exists $ u \in \ZZ\sbr{\sqrt{d}}^\times $ such that $ \N\br{u} = -1 $. Given such a $ u $, all solutions to the equation are given by $ \pm u\epsilon^n $ for $ n \in \ZZ $, since $ \N\br{v} = -1 $ if and only if $ \N\br{v} = \N\br{u} $, if and only if $ \N\br{v / u} = 1 $.

\begin{example*}
If $ d = 3 $, there are no solutions, as $ X^2 \equiv -1 \mod 3 $ has no solutions.
\end{example*}

\pagebreak

\section{Continued fractions}

\subsection{Rational continued fractions}

Let $ p / q \in \QQ $. Write
$$ \dfrac{p}{q} = a_0 + r_0, \qquad a_0 = \fbr{\dfrac{p}{q}} \in \ZZ, \qquad 0 \le r_0 < 1. $$
If $ r_i \ne 0 $, write
$$ \dfrac{1}{r_i} = a_{i + 1} + r_{i + 1}, \qquad a_{i + 1} = \fbr{\dfrac{1}{r_i}} \in \ZZ_{\ge 1}, \qquad 0 \le r_{i + 1} < 1. $$
Eventually get some $ r_n = 0 $. Write
$$ \dfrac{p}{q} = a_0 + \dfrac{1}{a_1 + \dfrac{1}{\dots + \dfrac{1}{a_n}}}. $$

\begin{example*}
$$ \dfrac{40}{19} = 2 + \dfrac{2}{19}, \qquad \dfrac{19}{2} = 9 + \dfrac{1}{2} \qquad \implies \qquad \dfrac{40}{19} = 2 + \dfrac{1}{9 + \dfrac{1}{2 + 0}}. $$
\end{example*}

\subsection{Infinite continued fractions}

Let $ \alpha \in \RR \setminus \QQ $. As above, set $ a_0 = \fbr{\alpha} $, write
$$ \alpha = a_0 + r_0, \qquad a_0 = \fbr{\alpha} \in \ZZ, \qquad 0 \le r_0 < 1. $$
Define sequences $ a_i $ and $ r_i $ by
$$ \dfrac{1}{r_i} = a_{i + 1} + r_{i + 1}, \qquad a_{i + 1} = \fbr{\dfrac{1}{r_i}} \in \ZZ_{\ge 1}, \qquad 0 \le r_{i + 1} < 1. $$
By definition, $ a_i \ge 1 $ if $ i > 0 $. Write
$$ \alpha = a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \dfrac{1}{\dots}}}. $$

\begin{example*}
Let $ \alpha = \sqrt{3} $. Then
\begin{align*}
& a_0 = 1, \qquad r_0 = \sqrt{3} - 1, \qquad \dfrac{1}{r_0} = \dfrac{1}{\sqrt{3} - 1} = \dfrac{\sqrt{3} + 1}{2} = 1 + \dfrac{\sqrt{3} - 1}{2}, \\
& a_1 = 1, \qquad r_1 = \dfrac{\sqrt{3} - 1}{2}, \qquad \dfrac{1}{r_1} = \dfrac{2}{\sqrt{3} - 1} = \sqrt{3} + 1 = 2 + \br{\sqrt{3} - 1}, \\
& a_2 = 2, \qquad r_2 = \sqrt{3} - 1 = r_0, \qquad \dfrac{1}{r_2} = \dfrac{1}{\sqrt{3} - 1} = \dfrac{1}{r_0},
\end{align*}
so
$$ a_i =
\begin{cases}
1 & i > 0 \ \text{odd} \\
2 & i > 0 \ \text{even}
\end{cases}.
$$
\end{example*}

If $ a_0, \dots, a_n \in \RR $, then
$$ \sbr{a_0; a_1, \dots, a_n} = a_0 + \dfrac{1}{a_1 + \dfrac{1}{\dots + \dfrac{1}{a_n}}}. $$

\pagebreak

\begin{lemma}
\label{lem:68}
If $ a_0, \dots, a_n \in \RR $, define $ p_i $ and $ q_i $ for $ 0 \le i \le n $ by
$$ p_0 = a_0, \qquad q_0 = 1, \qquad p_1 = a_0a_1 + 1, \qquad q_1 = a_1, \qquad p_i = a_ip_{i - 1} + p_{i - 2}, \qquad q_i = a_iq_{i - 1} + q_{i - 2}. $$
Assuming that no $ q_i = 0 $, we have $ \sbr{a_0; a_1, \dots, a_n} = p_n / q_n $.
\end{lemma}

\begin{proof}
Induction on $ n $.
\begin{itemize}[leftmargin=0.5in]
\item[$ n = 0 $.] $ a_0 = a_0 / 1 $ is trivial.
\item[$ n = 1 $.] $ a_0 + 1 / a_1 = \br{a_0a_1 + 1} / a_1 $ is trivial.
\item[$ n > 1 $.] Define sequences $ p_i' $ and $ q_i' $ for $ 0 \le i \le n - 1 $ by applying the definition to the sequence
$$ a_0, \dots, a_{n - 2}, a_{n - 1} + \dfrac{1}{a_n}. $$
By definition, $ p_i' = p_i $ and $ q_i' = q_i $ if $ i \le n - 2 $. By induction,
$$ \sbr{a_0; a_1, \dots, a_{n - 2}, a_{n - 1} + \dfrac{1}{a_n}} = \dfrac{p_{n - 1}'}{q_{n - 1}'}. $$
By definition,
$$ \sbr{a_0; a_1, \dots, a_n} = \sbr{a_0; a_1, \dots, a_{n - 2}, a_{n - 1} + \dfrac{1}{a_n}}. $$
So we only need to show that $ p_{n - 1}' / q_{n - 1}' = p_n / q_n $, and
\begin{align*}
\dfrac{p_{n - 1}'}{q_{n - 1}'}
& = \dfrac{\br{a_{n - 1} + 1 / a_n}p_{n - 2}' + p_{n - 3}'}{\br{a_{n - 1} + 1 / a_n}q_{n - 2}' + q_{n - 3}'}
= \dfrac{\br{a_{n - 1} + 1 / a_n}p_{n - 2} + p_{n - 3}}{\br{a_{n - 1} + 1 / a_n}q_{n - 2} + q_{n - 3}} \\
& = \dfrac{\br{a_na_{n - 1} + 1}p_{n - 2} + a_np_{n - 3}}{\br{a_na_{n - 1} + 1}q_{n - 2} + a_nq_{n - 3}}
= \dfrac{a_n\br{a_{n - 1}p_{n - 2} + p_{n - 3}} + p_{n - 2}}{a_n\br{a_{n - 1}q_{n - 2} + q_{n - 3}} + q_{n - 2}}
= \dfrac{a_np_{n - 1} + p_{n - 2}}{a_nq_{n - 1} + q_{n - 2}}
= \dfrac{p_n}{q_n}.
\end{align*}
\end{itemize}
\end{proof}

Suppose now that $ a_i \ge 1 $ if $ i \ge 1 $. Then $ q_i = a_iq_{i - 1} + q_{i - 2} \ge q_{i - 1} + q_{i - 2} $. So the $ q_i $ form an increasing sequence, in fact with $ q_i \ge q_{i - 1} + q_{i - 2} \ge 2q_{i - 2} $, so it even increases exponentially. If $ a_0, a_1, \dots \in \RR $ is an infinite sequence with $ a_i \ge 1 $ for all $ i $, say that $ p_i / q_i $ is the \textbf{$ i $-th convergent} to
$$ a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \dfrac{1}{\dots}}}. $$

\begin{lemma}
\label{lem:69}
For all $ n $,
$$ p_nq_{n - 1} - q_np_{n - 1} = \br{-1}^{n - 1}. $$
\end{lemma}

\begin{proof}
Obvious for $ n = 1 $. For the inductive step,
\begin{align*}
p_nq_{n - 1} - q_np_{n - 1}
& = \br{a_np_{n - 1} + p_{n - 2}}q_{n - 1} - \br{a_nq_{n - 1} + q_{n - 2}}p_{n - 1} \\
& = p_{n - 2}q_{n - 1} - q_{n - 2}p_{n - 1} \\
& = -\br{p_{n - 1}q_{n - 2} - q_{n - 1}p_{n - 2}}.
\end{align*}
\end{proof}

\begin{note*}
If $ a_i \in \ZZ $, then $ p_i, q_i \in \ZZ $, and Lemma \ref{lem:69} implies that $ \br{p_n, q_n} = 1 $. In general, Lemma \ref{lem:69} implies that
$$ \abs{\dfrac{p_n}{q_n} - \dfrac{p_{n - 1}}{q_{n - 1}}} = \dfrac{1}{q_nq_{n - 1}}. $$
If $ a_i \ge 1 $ for all $ i \ge 1 $, then the sequence $ q_i $ increases exponentially. So $ \sum_{i = 1}^n 1 / q_iq_{i - 1} $ converges, so that $ \br{p_n / q_n} $ is a Cauchy sequence, so it converges.
\end{note*}

\pagebreak

\lecture{20}{Tuesday}{20/11/18}

\begin{lemma}
\label{lem:70}
Let $ \alpha \in \RR \setminus \QQ $, and let $ \sbr{a_0; a_1, a_2, \dots} $ be the corresponding continued fraction. Then $ p_n / q_n < \alpha $ if $ n $ is even, and $ p_n / q_n > \alpha $ if $ n $ is odd.
\end{lemma}

\begin{proof}
Induction on $ n $.
\begin{itemize}[leftmargin=0.5in]
\item[$ n = 0 $.] $ a_0 = \fbr{\alpha} < \alpha $ and $ p_0 / q_0 = a_0 / 1 = a_0 $.
\item[$ n $ odd.] By induction, we have $ \sbr{a_1; a_2, \dots, a_n} < 1 / \br{\alpha - a_0} $, since $ \alpha = a_0 + 1 / \br{a_1 + 1 / \dots} $. That is, $ \alpha - a_0 < 1 / \sbr{a_1; a_2, \dots, a_n} $, that is
$$ \alpha < a_0 + \dfrac{1}{\sbr{a_1; a_2, \dots, a_n}} = \sbr{a_0; a_1, \dots, a_n} = \dfrac{p_n}{q_n}. $$
\item[$ n $ even.] The same argument with $ > $.
\end{itemize}
\end{proof}

\begin{corollary}
Assume $ \alpha \in \RR \setminus \QQ $ and $ a_0, a_1, \dots \in \ZZ $ be coming from its continued fraction. Let $ p_n / q_n = \sbr{a_0; a_1, \dots, a_n} $ be the $ n $-th convergent. Then
$$ \abs{\alpha - \dfrac{p_n}{q_n}} < \dfrac{1}{q_nq_{n + 1}}. $$
In particular, $ p_n / q_n \to \alpha $ as $ n \to \infty $.
\end{corollary}

\begin{proof}
Either $ p_n / q_n < \alpha < p_{n + 1} / q_{n + 1} $ or $ p_n / q_n > \alpha > p_{n + 1} / q_{n + 1} $, by Lemma \ref{lem:70}. Either way,
$$ \abs{\dfrac{p_n}{q_n} - \alpha} < \abs{\dfrac{p_n}{q_n} - \dfrac{p_{n + 1}}{q_{n + 1}}} \le \dfrac{1}{q_nq_{n + 1}}, $$
by Lemma \ref{lem:69}.
\end{proof}

\begin{note*}
$ 1 / q_nq_{n + 1} < 1 / q_n^2 $, so the sequence $ \br{p_n / q_n} $ satisfies the requirements of Dirichlet's theorem.
\end{note*}

\subsection{Best approximations}

Fix $ \alpha \in \RR \setminus \QQ $. Define $ a_i $ and $ r_i $ by
$$ \alpha = a_0 + r_0, \qquad a_0 = \fbr{\alpha} \in \ZZ, \qquad 0 < r_0 < 1, $$
If $ i \ge 1 $,
$$ \dfrac{1}{r_i} = a_{i + 1} + r_{i + 1}, \qquad a_{i + 1} = \fbr{\dfrac{1}{r_i}} \in \ZZ_{\ge 1}, \qquad 0 < r_{i + 1} < 1. $$

\begin{lemma}
\label{lem:72}
For all $ n $,
$$ \alpha = \dfrac{p_n + p_{n - 1}r_n}{q_n + q_{n - 1}r_n}. $$
\end{lemma}

\begin{proof}
$ \alpha = \sbr{a_0; a_1, \dots, a_n, 1 / r_n} $, so set $ p_{n + 1} = p_n / r_n + p_{n - 1} $ and $ q_{n + 1} = q_n / r_n + q_{n - 1} $. Then by Lemma \ref{lem:68},
$$ \alpha = \dfrac{p_{n + 1}}{q_{n + 1}} = \dfrac{p_n / r_n + p_{n - 1}}{q_n / r_n + q_{n - 1}} = \dfrac{p_n + p_{n - 1}r_n}{q_n + q_{n - 1}r_n}. $$
\end{proof}

\begin{corollary}
For all $ n $,
$$ \abs{\alpha q_n - p_n} < \abs{\alpha q_{n - 1} - p_{n - 1}}, \qquad \abs{\alpha - \dfrac{p_n}{q_n}} < \abs{\alpha - \dfrac{p_{n - 1}}{q_{n - 1}}}. $$
\end{corollary}

\begin{proof}
By Lemma \ref{lem:72}, $ \alpha\br{q_n + q_{n - 1}r_n} = p_n + p_{n - 1}r_n $, so $ \alpha q_n - p_n = r_n\br{p_{n - 1} - \alpha q_{n - 1}} $. So $ \abs{\alpha q_n - p_n} = r_n\abs{\alpha q_{n - 1} - p_{n - 1}} < \abs{\alpha q_{n - 1} - p_{n - 1}} $, so
$$ \abs{\alpha - \dfrac{p_n}{q_n}} = \dfrac{1}{q_n}\abs{\alpha q_n - p_n} < \dfrac{1}{q_n}\abs{\alpha q_{n - 1} - p_{n - 1}} < \dfrac{1}{q_{n - 1}}\abs{\alpha q_{n - 1} - p_{n - 1}} = \abs{\alpha - \dfrac{p_{n - 1}}{q_{n - 1}}}. $$
\end{proof}

\pagebreak

\begin{theorem}
\label{thm:74}
Let $ h, k \in \ZZ $ and $ 0 < \abs{k} < q_{n + 1} $. Then
$$ \abs{k\alpha - h} \ge \abs{\alpha q_n - p_n}, $$
with equality only if $ \abs{k} = q_n $. If $ \abs{k} \le q_n $, then
$$ \abs{\dfrac{h}{k} - \alpha} \ge \abs{\dfrac{p_n}{q_n} - \alpha}, $$
with equality if and only if $ h / k = p_n / q_n $.
\end{theorem}

\begin{proof}
By Lemma \ref{lem:69} there exist $ u, v \in \ZZ $ such that $ h = up_n + vp_{n + 1} $ and $ k = uq_n + vq_{n + 1} $, since
$$ \twobyone{h}{k} = \twobytwo{p_n}{p_{n + 1}}{q_n}{q_{n + 1}}\twobyone{u}{v} \qquad \iff \qquad \twobyone{u}{v} = \twobytwo{p_n}{p_{n + 1}}{q_n}{q_{n + 1}}^{-1}\twobyone{h}{k} = \dfrac{1}{\br{-1}^n}\twobytwo{q_{n + 1}}{-p_{n + 1}}{-q_n}{p_n}\twobyone{h}{k}. $$
By assumption, $ 0 < \abs{k} < q_{n + 1} $. So $ u \ne 0 $, else $ k = vq_{n + 1} $, so $ \abs{v} < 1 $ is a contradiction. If $ v \ne 0 $, then $ u $ and $ v $ have opposite signs, else
$$ \abs{k} = \abs{uq_n} + \abs{vq_{n + 1}} \ge q_n + q_{n + 1} > q_{n + 1}. $$
If $ v = 0 $, then $ h = up_n $ and $ k = uq_n $, and everything is easy. If $ v \ne 0 $, then write
$$ k\alpha - h = u\br{\alpha q_n - p_n} + v\br{\alpha q_{n + 1} - p_{n + 1}}. $$
Then $ u $ and $ v $ have opposite signs. By Lemma \ref{lem:70}, $ \alpha q_n - p_n $ and $ \alpha q_{n + 1} - p_{n + 1} $ also have opposite signs. So $ u\br{\alpha q_n - p_n} $ and $ v\br{\alpha q_{n + 1} - p_{n + 1}} $ have the same sign. So
$$ \abs{k\alpha - h} = \abs{u\br{\alpha q_n - p_n}} + \abs{v\br{\alpha q_{n + 1} - p_{n + 1}}} > \abs{\alpha q_n - p_n}, $$
if $ u, v \ne 0 $. For the last part, if $ \abs{k} \le q_n $ then $ 1 / \abs{k} \ge 1 / q_n $. So $ \abs{k\alpha - h} / \abs{k} \ge \abs{q_n\alpha - p_n} / q_n $, that is $ \abs{\alpha - h / k} \ge \abs{\alpha - p_n / q_n} $.
\end{proof}

\begin{corollary}
\label{cor:75}
If $ h, k \in \ZZ $ with $ \abs{\alpha - h / k} < 1 / 2k^2 $, then
$$ \dfrac{h}{k} = \dfrac{p_n}{q_n}, $$
for some $ n $.
\end{corollary}

\begin{proof}
Without loss of generality $ k \ge 1 $, and $ q_n \le k < q_{n + 1} $ for some $ n $. Then
\begin{align*}
\abs{\dfrac{p_n}{q_n} - \dfrac{h}{k}}
& \le \abs{\dfrac{p_n}{q_n} - \alpha} + \abs{\alpha - \dfrac{h}{k}}
= \dfrac{1}{q_n}\abs{\alpha q_n - p_n} + \dfrac{1}{k}\abs{\alpha k - h} \\
& \le \br{\dfrac{1}{q_n} + \dfrac{1}{k}}\abs{\alpha k - h}
= k\br{\dfrac{1}{q_n} + \dfrac{1}{k}}\abs{\alpha - \dfrac{h}{k}}
< \dfrac{1}{2k}\abs{\dfrac{1}{q_n} + \dfrac{1}{k}}
\le \dfrac{1}{kq_n},
\end{align*}
by Theorem \ref{thm:74}. So $ \abs{p_n / q_n - h / k} < 1 / kq_n $. So $ p_n / q_n - h / k = 0 $, as required.
\end{proof}

\subsection{Returning to Pell's equation}

\lecture{21}{Wednesday}{21/11/18}

Pell's equation is $ x^2 - dy^2 = 1 $. If $ \br{x, y} $ is a solution, then $ \abs{\sqrt{d} - x / y} $ is small.

\begin{proposition}
Let $ d > 1 $ be squarefree, and let $ p_n / q_n $ be the sequence of convergents for the continued fraction for $ \sqrt{d} $. If $ x, y > 0 $ with $ x^2 - dy^2 = \pm 1 $, then $ x = p_n $ and $ y = q_n $ for some $ n $.
\end{proposition}

\begin{proof}
\hfill
\begin{itemize}
\item Firstly suppose $ x^2 - dy^2 = 1 $. It is enough to show that $ x / y = p_n / q_n $ for some $ n $. Since $ \br{p_n, q_n} = 1 $, this implies that $ x = rp_n $ and $ y = rq_n $ for some $ r $, and then $ 1 = x^2 - dy^2 = r^2\br{p_n^2 - dq_n^2} $, so $ r = 1 $. By Corollary \ref{cor:75}, it suffices to prove that $ \abs{\sqrt{d} - x / y} < 1 / 2y^2 $. Since $ x - y\sqrt{d} = 1 / \br{x + y\sqrt{d}} > 0 $, so $ x > y\sqrt{d} $, and $ x / y > \sqrt{d} $. So
$$ \abs{\dfrac{x}{y} - \sqrt{d}} = \dfrac{x}{y} - \sqrt{d} = \dfrac{1}{y}\br{x - y\sqrt{d}} = \dfrac{1}{y}\br{\dfrac{1}{x + y\sqrt{d}}} < \dfrac{1}{y}\br{\dfrac{1}{y\sqrt{d} + y\sqrt{d}}} = \dfrac{1}{2\sqrt{d}y^2} < \dfrac{1}{2y^2}. $$

\pagebreak

\item Now assume $ x^2 - dy^2 = -1 $. Again enough to show that $ x / y = p_n / q_n $. Trick is to rewrite as $ y^2 - x^2 / d = 1 / d $. Then $ y - x / \sqrt{d} = \br{1 / d} / \br{y + x / \sqrt{d}} > 0 $. So $ y > x / \sqrt{d} $, so
$$ \abs{\dfrac{y}{x} - \dfrac{1}{\sqrt{d}}} = \dfrac{y}{x} - \dfrac{1}{\sqrt{d}} = \dfrac{1}{x}\br{y - \dfrac{x}{\sqrt{d}}} = \dfrac{1}{x}\br{\dfrac{1 / d}{y + x / \sqrt{d}}} < \dfrac{1}{x}\br{\dfrac{1 / d}{x / \sqrt{d} + x / \sqrt{d}}} = \dfrac{1 / \sqrt{d}}{2x^2} < \dfrac{1}{2x^2}. $$
So Corollary \ref{cor:75} implies that $ y / x $ is a convergent for the continued fraction of $ 1 / \sqrt{d} $. Then $ \fbr{1 / \sqrt{d}} = 0 $, so the continued fraction for $ 1 / \sqrt{d} $ is of the form $ \sbr{0; a_0, a_1, \dots} $. The next step is $ 1 / \br{1 / \sqrt{d}} = \sqrt{d} $. So if $ \sqrt{d} = \sbr{a_0; a_1, a_2, \dots} $, then $ 1 / \sqrt{d} = \sbr{0; a_0, a_1, \dots} $, since
$$ \sqrt{d} = a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \dfrac{1}{\dots}}}, \qquad \dfrac{1}{\sqrt{d}} = 0 + \dfrac{1}{a_0 + \dfrac{1}{a_1 + \dfrac{1}{\dots}}}. $$
So the convergents for $ 1 / \sqrt{d} $ are the $ q_n / p_n $. So $ y / x = q_n / p_n $ for some $ n $, and $ x / y = p_n / q_n $.
\end{itemize}
\end{proof}

\begin{example*}
\hfill
\begin{itemize}
\item $ \sqrt{3} = \sbr{1; 1, 2, 1, 2, \dots} = \sbr{1; \overline{1, 2}} $.
\item $ \sqrt{2} = 1 + \br{\sqrt{2} - 1} $, $ 1 / \br{\sqrt{2} - 1} = \sqrt{2} + 1 = 2 + \br{\sqrt{2} - 1} $, so $ \sqrt{2} = \sbr{1; \overline{2}} $.
\item $ \sqrt{5} = 2 + \br{\sqrt{5} - 2} $, $ 1 / \br{\sqrt{5} - 2} = \sqrt{5} + 2 = 4 + \br{\sqrt{5} - 2} $, so $ \sqrt{5} = \sbr{2; \overline{4}} $.
\item $ \sqrt{7} = \sbr{2; \overline{1, 1, 1, 4}} $.
\item $ \sqrt{13} = \sbr{3; \overline{1, 1, 1, 1, 6}} $.
\item $ \sqrt{43} = \sbr{6; \overline{1, 1, 3, 1, 5, 1, 3, 1, 1, 12}} $.
\end{itemize}
\end{example*}

\begin{definition}
We say that $ \sbr{a_0; a_1, a_2, \dots} $ is \textbf{eventually periodic} if there exist $ N, d > 0 $ such that $ a_{n + d} = a_n $ for all $ n \ge N $. We say that it is \textbf{periodic} if we can take $ N = 0 $.
\end{definition}

\begin{fact}
The following are facts.
\begin{itemize}
\item The continued fraction of $ \sqrt{d} $ is eventually periodic.
\item In fact, it is of the form
$$ \sbr{a_0; \overline{a_1, \dots, a_{m - 1}, 2a_0}}. $$
\item $ a_1, \dots, a_{m - 1} $ is symmetric, that is $ a_i = a_{m - i} $ for $ 1 \le i \le m - 1 $.
\item The $ n $ for which $ p_n^2 - dq_n^2 = \pm 1 $ are exactly the $ n $ for which $ n \equiv -1 \mod m $. If $ n = lm - 1 $, then
$$ p_n^2 - dq_n^2 = \br{-1}^{lm}. $$
\item The fundamental $ 1 $-unit is
$$
\begin{cases}
p_{m - 1} + q_{m - 1}\sqrt{d} & m \ \text{even} \\
p_{2m - 1} + q_{2m - 1}\sqrt{d} & m \ \text{odd}
\end{cases}.
$$
\item There is a solution to $ x^2 - dy^2 = -1 $ if and only if $ m $ is odd, in which case the solutions are
$$ \br{x, y} = \br{p_n, q_n}, \qquad n \equiv m - 1 \mod 2m. $$
\end{itemize}
\end{fact}

\pagebreak

\begin{example*}
\hfill
\begin{itemize}
\item Let $ x^2 - 43y^2 = \pm 1 $, so $ m = 10 $ is even, so there are no solutions to $ x^2 - 43y^2 = -1 $. The smallest solution for $ x^2 - 43y^2 = 1 $ is $ p_9 $ and $ q_9 $. Then
$$
\begin{array}{c|cccccccccc}
i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline
a & 6 & 1 & 1 & 3 & 1 & 5 & 1 & 3 & 1 & 1 \\
p & 6 & 7 & 13 & 46 & 59 & 341 & 400 & 1541 & 1941 & 3482 \\
q & 1 & 1 & 2 & 7 & 9 & 52 & 61 & 235 & 296 & 531
\end{array},
$$
so $ p_9 = 3482 $, so $ 3482^2 - 43\br{531}^2 = 1 $ is the smallest solution.
\item For $ 13 $, $ m = 5 $ so $ p_4 $ and $ q_4 $ is the smallest solution for $ x^2 - 13y^2 = -1 $ and $ p_9 $ and $ q_9 $ is the smallest solution for $ x^2 - 13y^2 = 1 $. Then
$$
\begin{array}{c|ccccc}
i & 0 & 1 & 2 & 3 & 4 \\
\hline
a & 3 & 1 & 1 & 1 & 1 \\
p & 3 & 4 & 7 & 11 & 18 \\
q & 1 & 1 & 2 & 3 & 5
\end{array},
$$
so $ 18^2 - 13\br{5}^2 = -1 $ is the smallest solution, and $ \N\br{18 + 5\sqrt{13}} = -1 $, so
$$ \N\br{\br{18 + 5\sqrt{13}}^2} = \N\br{649 + 180\sqrt{13}} = 1. $$
In fact, it follows from our facts that this is the fundamental $ 1 $-unit, that is $ p_9 + q_9\sqrt{13} $.
\end{itemize}
\end{example*}

\subsection{Periodic continued fractions}

\lecture{22}{Friday}{23/11/18}

\begin{definition}
$ \alpha \in \RR \setminus \QQ $ is a \textbf{quadratic irrational} if it is a root of some $ aX^2 + bX + c = 0 $, for $ a, b, c \in \QQ $ not all zero.
\end{definition}

\begin{proposition}
If $ \alpha $ has an eventually periodic continued fraction, then $ \alpha $ is a quadratic irrational.
\end{proposition}

\begin{proof}
\hfill
\begin{itemize}
\item Suppose firstly that the continued fraction of $ \alpha $ is periodic. Suppose $ a_{n + d} = a_n $ for all $ n $, for some $ d \ge 1 $. Then
$$ \alpha = a_0 + \dfrac{1}{a_1 + \dfrac{1}{\dots + \dfrac{1}{a_{d - 1} + \dfrac{1}{\alpha}}}}. $$
This gives an equation of the form $ \alpha = \br{x\alpha + y} / \br{z\alpha + w} $ for $ w, x, y, z \in \ZZ $, by applying Lemma \ref{lem:72} to $ \sbr{a_0; a_1, \dots, a_{d - 1}, \alpha} $. Then $ \br{z\alpha + w}\alpha - \br{x\alpha + y} = 0 $, that is $ z\alpha^2 + \br{w - x}\alpha - y = 0 $. Since $ \alpha \in \RR \setminus \QQ $, we conclude that $ \alpha $ is a quadratic irrational.
\item Suppose now that $ \alpha $ is only eventually periodic. Then
$$ \alpha = a_0 + \dfrac{1}{a_1 + \dfrac{1}{\dots + \dfrac{1}{a_N + \dfrac{1}{\beta}}}}, $$
where $ \beta $ has a periodic continued fraction. So $ \beta $ is a quadratic irrational. To complete the proof, we need to show that if $ \gamma $ is a quadratic irrational, then $ 1 / \gamma $ and $ \gamma + n $ are quadratic irrationals for any $ n \in \ZZ $. If $ \gamma $ is a root of $ aX^2 + bX + c = 0 $, then $ 1 / \gamma $ is a root of $ cX^2 + bX + a = 0 $, and $ \gamma + n $ is a root of $ a\br{X - n}^2 + b\br{X - n} + c = 0 $.
\end{itemize}
\end{proof}

In fact, the converse is also true. All quadratic irrationals have eventually periodic continued fractions.

\pagebreak

\section{Diophantine approximation}

\subsection{Liouville's theorem}

\begin{definition}
Let $ d \in \ZZ_{\ge 1} $. Then $ \alpha \in \CC $ is \textbf{algebraic of degree $ d $} if there exists a polynomial of degree $ d $ with integer coefficients and $ \alpha $ as a root, and there does not exist such a polynomial of smaller degree.
\end{definition}

\begin{example*}
$ d = 1 $ is $ \QQ $ and $ d = 2 $ is the quadratic irrationals.
\end{example*}

\begin{theorem}[Liouville's theorem]
Let $ \alpha \in \RR $ be algebraic of degree $ d $. Then for any $ e \in \RR_{> d} $, there are only finitely many $ p / q \in \QQ $ with
$$ \abs{\dfrac{p}{q} - \alpha} < \dfrac{1}{q^e}. $$
\end{theorem}

\begin{proof}
Let $ P\br{X} $ be a polynomial of degree $ d $ with coefficients in $ \ZZ $, with $ P\br{\alpha} = 0 $. Choose $ \epsilon > 0 $ such that the only root of $ P\br{X} $ in $ \sbr{\alpha - \epsilon, \alpha + \epsilon} $ is $ \alpha $. Write $ P\br{X} = \br{X - \alpha}Q\br{X} $. Then $ Q\br{X} $ is a polynomial of degree $ d - 1 $ with real coefficients, so in particular it is continuous, so there exists $ K $ such that $ \abs{Q\br{x}} \le K $ for $ x \in \sbr{\alpha - \epsilon, \alpha + \epsilon} $. Assume that $ \abs{p / q - \alpha} < 1 / q^e $. We may assume that $ q $ is large enough that $ 1 / q^e < \epsilon $. Since $ P $ has integer coefficients and is of degree $ d $, we have $ \abs{P\br{p / q}} \ge 1 / q^d $. Note that $ P\br{p / q} \ne 0 $, or we could replace $ P $ by $ P' $ with $ P\br{X} = \br{qX - p}P'\br{X} $. Since $ \abs{p / q - \alpha} < \epsilon $, $ p / q \in \sbr{\alpha - \epsilon, \alpha + \epsilon} $, so
$$ \dfrac{1}{q^d} \le \abs{P\br{\dfrac{p}{q}}} = \abs{\dfrac{p}{q} - \alpha} \abs{Q\br{\dfrac{p}{q}}} \le K \abs{\dfrac{p}{q} - \alpha} < \dfrac{K}{q^e}. $$
So $ K > q^{e - d} $, so $ K^{1 / \br{e - d}} > q $. So there are only finitely many possible $ q $, so only finitely many $ p / q $.
\end{proof}

\subsection{Constructing transcendentals}

Recall that $ \alpha \in \CC $ is \textbf{algebraic} if it is algebraic of some degree $ d $, and otherwise it is \textbf{transcendental}. The set of polynomials with integer coefficients is countable, so the set of algebraic numbers is countable. Since $ \RR $ is uncountable, transcendental numbers exist. Liouville's theorem gives a criterion. If for every $ e > 0 $, there are infinitely many $ p / q $ with $ \abs{\alpha - p / q} < 1 / q^e $, then $ \alpha $ cannot be algebraic.

\begin{example*}
Let $ \alpha = \sum_{n \ge 1} 10^{-n!} $ and $ \alpha_k = \sum_{n = 1}^k 10^{-n!} $. Then $ \alpha_k $ is rational with denominator $ q = 10^{k!} $, and
$$ \abs{\alpha - \alpha_k} = \sum_{n = k + 1}^\infty \dfrac{1}{10^{n!}} = \dfrac{1}{10^{\br{k + 1}!}}\br{1 + \dfrac{1}{10^{\br{k + 2}! - \br{k + 1}!}} + \dots} = \dfrac{1}{q^{k + 1}}\br{1 + \dfrac{1}{10^{k + 1}} + \dots} < \dfrac{2}{q^{k + 1}}. $$
If $ d \in \ZZ_{> 0} $, and $ k > d $, then $ 2 / q^{k + 1} < 1 / q^d $. So there exist infinitely many $ p / q = \alpha_k $ such that $ \abs{\alpha - p / q} < 1 / q^d $. Take $ d $ arbitrarily large, so $ \alpha $ is transcendental.
\end{example*}

\subsection{Roth's theorem}

\lecture{23}{Tuesday}{27/11/18}

\begin{theorem}[Roth's theorem]
Suppose that $ \alpha $ is algebraic. Then for any $ \epsilon > 0 $, there exist only finitely many $ x / y \in \QQ $ with $ \abs{\alpha - x / y} < 1 / y^{2 + \epsilon} $.
\end{theorem}

This can be used to show that many more numbers are transcendental than Liouville's theorem could.

\begin{example*}
$ \sum_{n \ge 1} 10^{-3^n} $ is transcendental.
\end{example*}

\begin{example*}
We saw that if $ d > 1 $ is squarefree, then $ x^2 - dy^2 = 1 $ has infinitely many solutions with $ x, y \in \ZZ $. Suppose now that $ d > 1 $, and consider $ x^3 - dy^3 = 1 $.
\begin{itemize}
\item $ d = e^3 $ is a cube. Then $ x^3 - dy^3 = x^3 - \br{ey}^3 = 1 $, so either $ \br{x, y} = \br{1, 0} $ or $ \br{x, y} = \br{0, 1} $ and $ d = 1 $.
\item $ d $ is not a cube. Then $ \sqrt[3]{d} \in \RR \setminus \QQ $ is algebraic, as $ X^3 - d = 0 $. Suppose $ x > 1 $, so $ x > \sqrt[3]{d}y $. Then
$$ x - \sqrt[3]{d}y = \dfrac{x^3 - dy^3}{x^2 + x\sqrt[3]{d}y + \sqrt[3]{d^2}y^2} = \dfrac{1}{x^2 + x\sqrt[3]{d}y + \sqrt[3]{d^2}y^2} < \dfrac{1}{3\sqrt[3]{d^2}y^2} = \dfrac{1}{3\sqrt[3]{d^2}y^2}. $$
So $ \abs{x / y - \sqrt[3]{d}} < 1 / 3\sqrt[3]{d^2}y^3 $. Choose any $ 0 < \epsilon < 1 $. Then $ 1 / 3\sqrt[3]{d^2}y^3 < 1 / y^{2 + \epsilon} $, for all $ y $ sufficiently large. So Roth's theorem tells us that there are only finitely many solutions. Similarly if $ x < 0 $.
\end{itemize}
\end{example*}

\pagebreak

\section{Primes in arithmetic progressions}

\subsection{Primes in arithmetic progressions}

A question is how are the prime numbers distributed modulo $ n $? Are there infinitely many primes congruent to $ a \mod n $ for each $ a $ and $ n $? The answer is no in general.

\begin{example*}
There are finitely many primes congruent to $ 2 \mod 4 $, or $ 0 \mod 2 $.
\end{example*}

If $ \br{a, n} \ne 1 $ then since any number is congruent to $ a \mod n $ is divisible by $ \br{a, n} $, we can have at most one prime. If $ \br{a, n} = 1 $, there is no obvious obstruction.

\begin{example*}
There are infinitely many primes congruent to $ 1 \mod 2 $.
\end{example*}

\begin{theorem}[Dirichlet's theorem]
If $ \br{a, n} = 1 $, then there are infinitely many primes congruent to $ a \mod n $.
\end{theorem}

We will prove this for $ a = 1 $.

\subsection{Elementary results}

\begin{theorem}
There are infinitely many primes.
\end{theorem}

\begin{proof}
Let $ S $ be a finite set of primes, and let
$$ Q = 1 + \prod_{p \in S} p. $$
Then $ Q > 1 $, so it has a prime factor $ q $. Then $ q \notin S $, so we are done.
\end{proof}

\begin{theorem}
There are infinitely many primes congruent to $ 3 \mod 4 $.
\end{theorem}

\begin{proof}
Let $ S $ be a finite set of primes which are congruent to $ 3 \mod 4 $. Let
$$ Q = 2 + \prod_{p \in S} p^2. $$
Then $ Q > 1 $, and $ Q \equiv 3 \mod 4 $, so $ Q $ has a prime factor $ q $ which has $ q \equiv 3 \mod 4 $. Then $ q \notin S $, so we are done.
\end{proof}

\begin{lemma}
\label{lem:87}
Let $ x $ be even, and $ p $ be a prime factor of $ x^2 + 1 $, then $ p \equiv 1 \mod 4 $.
\end{lemma}

\begin{proof}
Certainly $ p $ is odd. Then $ x^2 + 1 \equiv 0 \mod p $, so $ x^2 \equiv -1 \mod p $, so $ \symbol{-1}{p} = 1 $, so $ p \equiv 1 \mod 4 $.
\end{proof}

\begin{theorem}
There are infinitely many primes congruent to $ 1 \mod 4 $.
\end{theorem}

\begin{proof}
Let $ S $ be a finite set of primes congruent to $ 1 \mod 4 $. Let
$$ Q = 1 + 4\prod_{p \in S} p^2 = 1 + \br{2\prod_{p \in S} p}^2. $$
Then $ Q > 1 $, and if $ q $ is a prime factor of $ Q $ then $ q \notin S $, and $ q \equiv 1 \mod 4 $ by Lemma \ref{lem:87}.
\end{proof}

The general idea is to find a polynomial $ P\br{x} $ such that every prime factor of $ P\br{nx} $ is congruent to $ a \mod n $, or at least one. Turns out that this can be done only when $ a^2 \equiv 1 \mod n $. We will find such polynomials for $ a = 1 $.

\begin{theorem}
For any prime $ q $, there are infinitely many primes congruent to $ 1 \mod q $.
\end{theorem}

\begin{definition}
The $ q $-th \textbf{cyclotomic polynomial} is
$$ \Phi_q\br{X} = \dfrac{X^q - 1}{X - 1} = X^{q - 1} + \dots + 1. $$
\end{definition}

\pagebreak

\begin{theorem}
\label{thm:91}
Let $ p \ne q $ be prime, and let $ a \in \ZZ $. Then $ p \mid \Phi_q\br{a} $ if and only if $ a $ has order $ q \mod p $.
\end{theorem}

\begin{proof}
$ a $ has order $ q \mod p $ if and only if $ a^q \equiv 1 \mod p $ and $ a \not\equiv 1 \mod p $. If $ p \mid \Phi_q\br{a} $ then $ p \mid a^q - 1 $. If also $ a \equiv 1 \mod p $, then $ \Phi_q\br{a} \equiv \Phi_q\br{1} \equiv q \not\equiv 0 \mod p $, a contradiction. Conversely if $ a^q \equiv 1 \mod p $ and $ a \not\equiv 1 \mod p $, then $ \br{a^q - 1} / \br{a - 1} \equiv 0 \mod p $.
\end{proof}

\lecture{24}{Wednesday}{28/11/18}

\begin{corollary}
\label{cor:92}
If $ p \ne q $ is prime, and $ a \in \ZZ $, and $ p \mid \Phi_q\br{a} $, then $ p \equiv 1 \mod q $.
\end{corollary}

\begin{proof}
By Theorem \ref{thm:91}, $ a $ has order $ q \mod p $. But $ a^{p - 1} \equiv 1 \mod p $, by Fermat's little theorem. So $ q \mid p - 1 $.
\end{proof}

\begin{theorem}
Let $ q $ be prime. Then there are infinitely many primes with $ p \equiv 1 \mod q $.
\end{theorem}

\begin{proof}
Let $ S $ be a finite set of primes which are congruent to $ 1 \mod q $. Let
$$ R = \prod_{p \in S} p. $$
Consider $ \Phi_q\br{qR} \ge qR + 1 > 1 $. Let $ p $ be a prime factor of $ \Phi_q\br{qR} $. By Corollary \ref{cor:92}, either $ p = q $, or $ p \equiv 1 \mod q $. Since $ \Phi_q\br{qR} = \br{qR}^{q - 1} + \dots + 1 \equiv 1 \mod qR $, so $ p \ne q $, $ p \notin S $, and $ p \equiv 1 \mod q $.
\end{proof}

\subsection{Cyclotomic polynomials}

\begin{definition}
Let $ n \in \ZZ_{\ge 1} $. Then
$$ \Phi_n\br{X} = \prod_{1 \le a \le n, \ \br{a, n} = 1} \br{X - e^{\tfrac{2\pi ai}{n}}}. $$
\end{definition}

\begin{lemma}
\label{lem:95}
For any $ n $, we have
$$ X^n - 1 = \prod_{d \mid n, \ d > 0} \Phi_d\br{X}. $$
\end{lemma}

\begin{proof}
Each side is a monic polynomial, so we just need to check that the roots are the same, with multiplicities. The left hand side are the $ n $-th roots of unity, with multiplicity one each. The right hand side is $ \Phi_d $, the primitive $ d $-th roots of unity, with multiplicity one. Each $ n $-th root of unity is a primitive $ d $-th root of unity for some unique $ d \mid n $. The result follows.
\end{proof}

From this it is easy to deduce the following.

\begin{lemma}
For any $ n \ge 1 $, $ \Phi_n\br{X} \in \ZZ\sbr{X} $.
\end{lemma}

\begin{proof}
By induction on $ n $. If $ n = 1 $, $ \Phi_1\br{X} = X - 1 $. Assume that the result holds for all $ d \mid n $ for $ d < n $. By Lemma \ref{lem:95}, if we set
$$ P\br{X} = \prod_{d \mid n, \ 0 < d < n} \Phi_d\br{X}, $$
then $ P\br{X} \in \ZZ\sbr{X} $, $ P\br{X} $ is monic, and $ X^n - 1 = \Phi_n\br{X}P\br{X} $. Write
$$ \Phi_n\br{X} = \sum_i a_iX^i, \qquad P\br{X} = \sum_i b_iX^i, $$
and assume that not all $ a_i \in \ZZ $. Let $ q $ be maximal with $ a_q \notin \ZZ $. Let $ e = \deg P $, so $ P\br{X} = X^e + b_{e - 1}X^{e - 1} + \dots + b_0 $. Then the coefficient of $ X^{q + e} $ in $ \Phi_n\br{X}P\br{X} $ is
$$ a_q + a_{q + 1}b_{e - 1} + \dots + a_{q + e}b_0, \qquad a_{q + 1}b_{e - 1} + \dots + a_{q + e}b_0 \in \ZZ. $$
Since $ \Phi_n\br{X}P\br{X} = X^n - 1 \in \ZZ\sbr{X} $, this is a contradiction.
\end{proof}

\pagebreak

\begin{definition}
Let $ F $ be any field, and let $ P\br{X} \in F\sbr{X} $. Then $ P'\br{X} $, the \textbf{derivative} of $ P\br{X} $, is defined as follows. If $ P\br{X} = \sum_{n = 0}^d a_nX^n $, then
$$ P'\br{X} = \sum_{n = 1}^d na_nX^{n - 1}. $$
\end{definition}

\begin{note*}
$ \br{P + Q}' = P' + Q' $ and $ \br{PQ}' = P'Q + PQ' $.
\end{note*}

\begin{lemma}
\label{lem:98}
Suppose that $ \br{X - \alpha}^2 $ divides $ P\br{X} $. Then $ \alpha $ is a root of both $ P $ and $ P' $.
\end{lemma}

\begin{proof}
Write $ P\br{X} = \br{X - \alpha}^2R\br{X} $. Then
$$ P'\br{X} = \br{X - \alpha}^2R'\br{X} + 2\br{X - \alpha}R\br{X} = \br{X - \alpha}\br{\br{X - \alpha}R'\br{X} + 2R\br{X}}. $$
\end{proof}

\begin{corollary}
\label{cor:99}
If $ p \nmid n $, then $ \Phi_n\br{X} $ has no repeated roots modulo $ p $.
\end{corollary}

\begin{proof}
It suffices to show that $ X^n - 1 $ has no repeated roots modulo $ p $. The derivative of $ X^n - 1 $ is $ nX^{n - 1} $, so its only root is zero, which is not a root of $ X^n - 1 $. So we are done by Lemma \ref{lem:98}.
\end{proof}

\begin{note*}
If $ n = p $,
$$ X^p - 1 \equiv \br{X - 1}^p \mod p, \qquad \Phi_p\br{X} \equiv \br{X - 1}^{p - 1} \mod p. $$
\end{note*}

\begin{theorem}
\label{thm:100}
Suppose $ p \nmid n $ and $ a \in \ZZ $. Then $ p \mid \Phi_n\br{a} $ if and only if $ a $ has order exactly $ n \mod p $.
\end{theorem}

\begin{proof}
Firstly suppose that $ a $ has order exactly $ n $. Then $ a $ is a root of $ X^n - 1 \mod p $, but not a root of $ X^d - 1 $ for any $ d \mid n $ for $ d < n $. Since $ \Phi_d\br{X} \mid X^d - 1 $, $ a $ cannot be a root of $ \Phi_d\br{X} $ for any $ d \mid n $ for $ d < n $. Let
\begin{equation}
\label{eq:4}
X^n - 1 = \Phi_n\br{X}\prod_{d \mid n, \ 0 < d < n} \Phi_d\br{X},
\end{equation}
so $ a $ is a root of $ \Phi_n\br{X} \mod p $, that is $ p \mid \Phi_n\br{a} $. Conversely, suppose that $ p \mid \Phi_n\br{a} $. Then $ a $ is a root of $ \Phi_n\br{X} \mod p $, so by $ \br{\ref{eq:4}} $, $ a $ is a root of $ X^n - 1 \mod p $. We need to show that $ a $ is not a root of $ X^d - 1 $ for any $ d \mid n $ for $ d < n $. Writing
$$ X^d - 1 = \prod_{e \mid d} \Phi_e\br{X}, $$
$ a $ would be a root of $ \Phi_e\br{X} $ for some $ e \mid d \mid n $. So by $ \br{\ref{eq:4}} $, $ a $ is a root of both $ \Phi_n\br{X} $ and $ \Phi_e\br{X} $, so $ a $ is a repeated root of $ X^n - 1 \mod p $. This contradicts Corollary \ref{cor:99}.
\end{proof}

\begin{corollary}
\label{cor:101}
If $ p \nmid n $, and $ a \in \ZZ $, then if $ p \mid \Phi_n\br{a} $, then $ p \equiv 1 \mod n $.
\end{corollary}

\begin{proof}
$ a $ has order $ n \mod p $ by Theorem \ref{thm:100}, so $ n \mid p - 1 $, by Fermat's little theorem.
\end{proof}

\subsection{Primes congruent to \texorpdfstring{$ 1 \mod n $}{1 mod n}}

We are now in a position to prove the following.

\begin{theorem}
If $ n \in \ZZ_{\ge 1} $, there are infinitely many primes $ p $ with $ p \equiv 1 \mod n $.
\end{theorem}

\begin{proof}
Let $ S $ be a finite set of primes congruent to $ 1 \mod n $, and let
$$ R = \prod_{p \in S} p. $$
For each $ k $, let $ Q_k = \Phi_n\br{knR} \in \ZZ $. Note that not all $ Q_k $ are $ \pm 1 $, since $ \Phi_n\br{X} $ is a non-constant polynomial. Thus choose $ k $ large enough that $ Q_k > 1 $, so there is a prime $ p $ dividing $ Q_k $. Since $ Q_k $ divides $ \br{knR}^n - 1 $, no prime dividing $ n $ or $ R $ can divide $ Q_k $. Thus $ p $ is not in $ S $, and by Corollary \ref{cor:101} $ p $ is congruent to $ 1 \mod n $.
\end{proof}

\lecture{25}{Friday}{30/11/18}

Lecture 25 is a problems class.

\pagebreak

\section{Arithmetic functions}

\lecture{26}{Tuesday}{04/12/18}

An \textbf{arithmetic function} is a function $ f : \ZZ_{\ge 1} \to \CC $, such as $ \Phi $.

\subsection{Dirichlet convolution}

The set of arithmetic functions is a ring in the following way. Addition is $ \br{f + g}\br{n} = f\br{n} + g\br{n} $. Multiplication is \textbf{Dirichlet convolution} $ f * g $,
$$ \br{f * g}\br{n} = \sum_{d \mid n, \ d \ge 1} f\br{d}g\br{\dfrac{n}{d}} = \sum_{a, b \ge 1, \ ab = n} f\br{a}g\br{b}. $$
We have $ f * g = g * f $ and $ f * \br{g * h} = \br{f * g} * h $, and both are given by
$$ \br{f * g * h}\br{n} = \sum_{a, b, c \ge 1, \ abc = n} f\br{a}g\br{b}h\br{c}. $$
Then $ f * \br{g + h} = f * g + f * h $. There exists a multiplicative unit $ \epsilon $, that is $ f * \epsilon = \epsilon * f = f $. This is easy to figure out. We need
$$ f\br{n} = \br{f * \epsilon}\br{n} = \sum_{ab = n} f\br{a}\epsilon\br{b}. $$

\begin{example*}
$ f\br{4} = f\br{4}\epsilon\br{1} + f\br{2}\epsilon\br{2} + f\br{1}\epsilon\br{4} $. This forces $ \epsilon\br{1} = 1 $ and $ \epsilon\br{2} = \epsilon\br{4} = 0 $.
\end{example*}

So
$$ \epsilon\br{n} =
\begin{cases}
1 & n = 1 \\
0 & n > 1
\end{cases}.
$$

\subsection{M\"obius inversion}

The \textbf{M\"obius function} $ \mu : \ZZ_{\ge 1} \to \CC $ is defined as follows.
$$ \mu\br{n} =
\begin{cases}
1 & n = 1 \\
\br{-1}^k & n = p_1 \dots p_k \ \text{is a product of distinct prime factors} \\
0 & \text{otherwise}
\end{cases}.
$$

\begin{lemma}
\label{lem:103}
If $ 1 $ is the function $ 1\br{n} = 1 $ for all $ n $, then $ 1 * \mu = \epsilon $.
\end{lemma}

\begin{proof}
$ \epsilon\br{1} = \br{1 * \mu}\br{1} = 1 \times 1 $. If $ n > 1 $, we just have to check that
$$ \sum_{d \mid n} \mu\br{d} = \sum_{ab = n} 1\br{a}\mu\br{b} = 0. $$
Let $ p_1, \dots, p_k $ be the distinct primes dividing $ n $. Then
$$ \sum_{d \mid n} \mu\br{d} = \sum_{\br{\epsilon_1, \dots, \epsilon_k}, \ \epsilon_i = 0, 1} \br{-1}^{\epsilon_1 + \dots + \epsilon_k} = \br{\sum_{\epsilon_1 = 0}^1 \br{-1}^{\epsilon_1}} \dots \br{\sum_{\epsilon_k = 0}^1 \br{-1}^{\epsilon_k}} = 0, \qquad n = \prod_{i = 1}^k p_i^{\epsilon_i}. $$
\end{proof}

\begin{proposition}[M\"obius inversion]
If $ f $ and $ g $ are arithmetic functions then $ g = f * 1 $ if and only if $ f = g * \mu $.
\end{proposition}

\begin{proof}
$ \br{f * 1} * \mu = f * \br{1 * \mu} = f * \epsilon = f $, by Lemma \ref{lem:103}, and $ \br{g * \mu} * 1 = g * \br{\mu * 1} = g * \epsilon = g $.
\end{proof}

\begin{example*}
Let $ \id\br{n} = n $. Then $ \id = \Phi * 1 $. That is, $ n = \sum_{d \mid n} \Phi\br{d} $. So $ \Phi = \id * \mu $. So
$$ \Phi\br{n} = \sum_{d \mid n} \mu\br{d}\dfrac{n}{d} = n\sum_{d \mid n} \dfrac{\mu\br{d}}{d}. $$
\end{example*}

\pagebreak

\section{The distribution of prime numbers}

Let $ \pi\br{X} $ be the number of primes $ p $ such that $ p \le X $.

\subsection{Reminder of asymptotic notation}

$ A \ll B $, or $ A = \O\br{B} $, means there exists a constant $ C > 0 $ such that $ \abs{A} \le CB $, and $ B \gg A $ means $ A \ll B $.

\begin{example*}
If $ x \ge 1 $, $ x \ll x^2 \ll e^x / x^{100} $.
\end{example*}

$ A \ll_k B $ means $ A \ll B $ with the constant $ C $ depending on $ k $.

\begin{example*}
$ kx \ll_k x $.
\end{example*}

$ A = \o\br{B} $ means for all $ \epsilon > 0 $ we have $ \abs{A} \le \epsilon B $ as some other specified parameter becomes large enough.

\begin{example*}
$ 1 / \log x = \o\br{1} $ as $ x \to \infty $.
\end{example*}

$ A \sim B $ means $ A = \br{1 + \o\br{1}}B $.

\subsection{The prime number theorem}

\begin{theorem}[Prime number theorem]
$$ \pi\br{X} \sim \dfrac{X}{\log X}, \qquad X \to \infty. $$
\end{theorem}

\begin{theorem}
There exist constants $ 0 < c_1 < 1 < c_2 $ such that for all sufficiently large $ X $,
$$ c_1\dfrac{X}{\log X} \le \pi\br{X} \le c_2\dfrac{X}{\log X}. $$
\end{theorem}

This implies that
$$ \pi\br{X} = \O\br{\dfrac{X}{\log X}}. $$

\lecture{27}{Wednesday}{05/12/18}

\begin{proof}
\hfill
\begin{itemize}
\item Firstly consider the lower bound. We will prove that for some $ C_1 > 1 $, we have
\begin{equation}
\label{eq:5}
\prod_{p \le 2n} \ge C_1^n.
\end{equation}
Given $ \br{\ref{eq:5}} $, we have
$$ \br{2n}^{\pi\br{2n}} \ge \prod_{p \le 2n} p \ge C_1^n. $$
Taking logarithms,
$$ \pi\br{2n} \ge \br{\dfrac{1}{2}\log C_1}\dfrac{2n}{\log 2n}. $$
This gives the lower bound if $ X = 2n \in \ZZ $ is even, but since $ \pi\br{X + 1} - \pi\br{X} \le 1 $, it is easy to get the lower bound for all $ X $. We will prove $ \br{\ref{eq:5}} $ by considering the prime factors of
$$ \binom{2n}{n} = \prod_{p \le 2n} p^{\v_p\br{n}}. $$
Claim that
\begin{enumerate}
\item if $ p > \sqrt{2n} $ then $ \v_p\br{n} \le 1 $,
\item for all $ p \le 2n $, $ p^{\v_p\br{n}} \le 2n $, and
\item $ \prod_{p \le 2n} p^{\v_p\br{n}} \ge 4^n / \br{2n + 1} $.
\end{enumerate}

\pagebreak

Suppose $ 1 $ to $ 3 $ are true. Then
\begin{align*}
\dfrac{4^n}{2n + 1}
& \le \prod_{p \le 2n} p^{\v_p\br{n}}
= \prod_{p \le \sqrt{2n}} p^{\v_p\br{n}} \prod_{\sqrt{2n} < p \le 2n} p^{\v_p\br{n}} & \text{by} \ 3 \\
& \le \br{2n}^{\pi\br{\sqrt{2n}}} \prod_{\sqrt{2n} < p \le 2n} p^{\v_p\br{n}} & \text{by} \ 2 \\
& \le \br{2n}^{\pi\br{\sqrt{2n}}} \prod_{\sqrt{2n} < p \le 2n} p & \text{by} \ 1 \\
& \le \br{2n}^{\pi\br{\sqrt{2n}}} \prod_{p \le 2n} p
\le \br{2n}^{\sqrt{2n}} \prod_{p \le 2n} p.
\end{align*}
So
$$ \prod_{p \le 2n} p \ge \dfrac{4^n}{\br{2n + 1}\br{2n}^{\sqrt{2n}}}. $$
For $ n $ sufficiently large, and any $ 4 > C_1 $, the right hand side is at least $ C_1^n $, that is if $ K > 1 $, $ K^n \ge \br{2n + 1}\br{2n}^{\sqrt{2n}} $ for all $ n $ sufficiently large. \footnote{Exercise}
\begin{enumerate}
\item In the first example sheet question $ 11 $, the exact power of $ p $ dividing $ m! $ is $ \sum_{i = 1}^\infty \fbr{m / p^i} $. So
$$ \binom{2n}{n} = \dfrac{\br{2n}!}{n!n!} \qquad \implies \qquad \v_p\br{n} = \sum_{i = 1}^\infty \br{\fbr{\dfrac{2n}{p^i}} - 2\fbr{\dfrac{n}{p^i}}}. $$
For any $ x \in \RR $, $ \fbr{2x} - 2\fbr{x} \ge 0 $, and in fact $ \fbr{2x} - 2\fbr{x} = 0 $ or $ \fbr{2x} - 2\fbr{x} = 1 $. If $ p > \sqrt{2n} $, then $ p^2 > 2n $, so all terms in the sum vanish if $ i \ge 2 $, so the sum is at most one.
\item Note that the terms in the sum are zero as soon as $ p^i > 2n $, that is
$$ i > \dfrac{\log 2n}{\log p} \qquad \implies \qquad \v_p\br{n} \le \dfrac{\log 2n}{\log p} \qquad \implies \qquad p^{\v_p\br{n}} \le 2n. $$
\item
$$ 4^n = 2^{2n} = \br{1 + 1}^{2n} = \sum_{i = 0}^{2n} \binom{2n}{i} \le \br{2n + 1}\binom{2n}{n} \qquad \implies \qquad \prod_{p \le 2n} p^{\v_p\br{n}} = \binom{2n}{n} \ge \dfrac{4^n}{2n + 1}. $$
\end{enumerate}
\item Claim that there exists $ C_2 > 1 $ such that for all $ X $ sufficiently large, we have
\begin{equation}
\label{eq:6}
\prod_{\tfrac{X}{2} \le p \le X} p \le C_2^X.
\end{equation}
Suppose we know $ \br{\ref{eq:6}} $. Then
$$ C_2^X \ge \prod_{\tfrac{X}{2} \le p \le X} p \ge \br{\dfrac{X}{2}}^{\pi\br{X} - \pi\br{\tfrac{X}{2}}}. $$
Taking logarithms,
\begin{equation}
\label{eq:7}
\pi\br{X} \le \pi\br{\dfrac{X}{2}} + \dfrac{X\log C_2}{\log \tfrac{X}{2}}.
\end{equation}
Suppose that $ X $ is large enough that $ \br{\ref{eq:6}} $ holds for $ X, \dots, X / 2^{m - 1} $. Substituting $ X, \dots, X / 2^{m - 1} $ into $ \br{\ref{eq:7}} $, and summing,
$$ \pi\br{X} \le \pi\br{\dfrac{X}{2^m}} + 2\log C_2\sum_{i = 1}^m \dfrac{\tfrac{X}{2^i}}{\log \tfrac{X}{2^i}}. $$

\pagebreak

Now fix $ X $ and choose $ m $ to be largest possible with $ 2^m \le \sqrt{X} $. Then $ X / 2^m \ge \sqrt{X} $, so $ \br{\ref{eq:6}} $ is indeed valid for $ X, \dots, X / 2^{m - 1} $ provided that $ X $ is sufficiently large. Since $ m $ is maximal such that $ 2^m \le \sqrt{X} $, we have $ 2^m \ge \sqrt{X} / 2 $. So
$$ \pi\br{\dfrac{X}{2^m}} \le \dfrac{X}{2^m} \le 2\sqrt{X}. $$
So substituting into the above,
$$ \pi\br{X} \le 2\sqrt{X} + 2\log C_2\sum_{i = 1}^m \dfrac{\tfrac{X}{2^i}}{\log \tfrac{X}{2^i}} \le 2\sqrt{X} + \dfrac{2\log C_2}{\tfrac{1}{2}\log X}\sum_{i = 1}^m \dfrac{X}{2^i} \le 2\sqrt{X} + \br{4\log C_2}\br{\dfrac{X}{\log X}}. $$
This gives our upper bound, because $ \sqrt{X} \ll X / \log X $. Now remains to prove $ \br{\ref{eq:6}} $. We saw above that if $ n \in \ZZ $ then
$$ \prod_{n < p \le 2n} p \le \binom{2n}{n} \le 4^n = \sum_{i = 0}^{2n} \binom{2n}{i}. $$
Take $ n = \fbr{X / 2} $. Then $ 2n \le X $, and we get
$$ \prod_{\tfrac{X}{2} < p \le 2\fbr{\tfrac{X}{2}}} p \le 2^{2n} \le 2^X \qquad \implies \qquad \prod_{\tfrac{X}{2} < p \le X} p \le X2^X < C_2^X, $$
for $ X $ sufficiently large, for any $ C_2 > 2 $.
\end{itemize}
\end{proof}

\lecture{28}{Friday}{07/12/18}

Lecture 28 is a problems class.

\subsection{The Brun-Titchmarsh theorem and the Selberg sieve}

\lecture{29}{Tuesday}{11/12/18}

What can we say about the number of primes $ p $ with $ X < p \le X + Y $? That is, $ \pi\br{X + Y} - \pi\br{X} $. Think of $ Y $ being fixed for a moment. The best possible lower bound is zero.

\begin{example*}
$ n! + 2, \dots, n! + n $ is a sequence of consecutive composite numbers.
\end{example*}

It was conjectured, in 1920s, by Hardy and Littlewood that $ \pi\br{X + Y} \le \pi\br{X} + \pi\br{Y} $, that is $ \pi\br{X + Y} - \pi\br{X} \le \pi\br{Y} $. This is no longer believed.

\begin{theorem}
\label{thm:107}
$$ \pi\br{X + Y} - \pi\br{X} \le \dfrac{\br{2 + \o\br{1}}Y}{\log Y}, $$
where $ \o\br{1} $ is as $ Y \to \infty $ and $ X $ is fixed.
\end{theorem}

In $ X + 1, \dots, X + Y $, about half of these are divisible by two, about a third of these are divisible by three, and about a sixth of these are divisible by six. If $ p_1, \dots, p_k $ are primes, the error term is $ 2^k $, so can only consider the first $ \log Y $ primes, which implies Theorem \ref{thm:107} for $ Y / \log \log Y $. Selberg's idea is to weight the inclusion-exclusion count.

\begin{proof}
Let $ \lambda_1, \lambda_2, \dots \in \RR $ be any sequence with $ \lambda_1 = 1 $. Let $ R < Y $ be fixed for now. Later we will choose $ R = Y^{\tfrac{1}{2} - \epsilon} $. Set
$$ \nu\br{n} = \br{\sum_{d \mid n, \ d \le R} \lambda_d}^2 \ge 0. $$
Suppose that $ p $ is prime, and $ p > R $. Then by definition, $ \nu\br{p} = \lambda_1^2 = 1 $, so
$$ \pi\br{X + Y} - \pi\br{X} = \sum_{X < p \le X + Y} 1 \le \pi\br{R} + \sum_{X < n \le X + Y} \nu\br{n} \le R + \sum_{X < n \le X + Y} \nu\br{n}. $$

\pagebreak

Now have to choose $ \lambda_i $ to minimise $ \sum_{X \le n \le X + Y} \nu\br{n} $, so
\begin{align*}
\sum_{X < n \le X + Y} \nu\br{n}
& = \sum_{X < n \le X + Y} \br{\sum_{d \mid n, \ d \le R} \lambda_d}^2
= \sum_{X < n \le X + Y} \br{\sum_{d_1 \mid n, \ d_1 \le R} \lambda_{d_1}}\br{\sum_{d_2 \mid n, \ d_2 \le R} \lambda_{d_2}} \\
& = \br{\sum_{d_1, d_2 \le R} \lambda_{d_1}\lambda_{d_2}}\br{\sum_{X < n \le X + Y, \ d_1 \mid n, \ d_2 \mid n} 1}
= \br{\sum_{d_1, d_2 \le R} \lambda_{d_1}\lambda_{d_2}}\br{\dfrac{Y\br{d_1, d_2}}{d_1d_2} + \O\br{1}},
\end{align*}
since $ \lcm\br{d_1, d_2} = d_1d_2 / \br{d_1, d_2} $. Putting this together,
$$ \pi\br{X + Y} - \pi\br{X} \le Y\sum_{d_1, d_2 \le R} \dfrac{\lambda_{d_1}\lambda_{d_2}\br{d_1, d_2}}{d_1d_2} + R + \O\br{1}\sum_{d_1, d_2 \le R} \abs{\lambda_{d_1}\lambda_{d_2}}, $$
where the leading term is
$$ Y\sum_{d_1, d_2 \le R} \dfrac{\lambda_{d_1}\lambda_{d_2}\br{d_1, d_2}}{d_1d_2}, $$
and the error term is
$$ R + \O\br{1}\sum_{d_1, d_2 \le R} \abs{\lambda_{d_1}\lambda_{d_2}}. $$
Now choose $ \lambda_i $ such that $ \lambda_1 = 1 $, in such a way as to minimise the leading term. Then choose $ R = Y^c $ for $ c < \tfrac{1}{2} $. Check that for any $ \epsilon > 0 $, we have $ \lambda_d \ll_\epsilon d^\epsilon $. Then
$$ \sum_{d_1d_2} \abs{\lambda_{d_1}\lambda_{d_2}} \le R^{2 + 2\epsilon} = Y^{2c\br{1 + \epsilon}}. $$
Choose $ \epsilon < 1 / 2c - 1 $, then $ Y^{2c\br{1 + \epsilon}} \ll Y / \log Y $. Write $ \overrightarrow{\lambda} = \br{\lambda_1, \lambda_2, \dots} $, so
$$ Q\br{\overrightarrow{\lambda}} = \sum_{d_1, d_2 \le R} \dfrac{\lambda_{d_1}\lambda_{d_2}\br{d_1, d_2}}{d_1d_2}. $$
Want to minimise this subject to $ \lambda_1 = 1 $. Want to diagonalise $ Q\br{\overrightarrow{\lambda}} $. Use, a slight variant of, M\"obius inversion. For any $ m $, $ m = \sum_{d \mid m} \Phi\br{d} $. Take $ m = \br{d_1, d_2} $. Then $ \br{d_1, d_2} = \sum_{\delta \mid \br{d_1, d_2}} \Phi\br{\delta} $, so
$$ Q\br{\overrightarrow{\lambda}} = \sum_{d_1, d_2 \le R} \dfrac{\lambda_{d_1}\lambda_{d_2}\br{d_1, d_2}}{d_1d_2} = \sum_{\delta \le R} \Phi\br{\delta}\br{\sum_{\delta \mid d, \ d \le R} \dfrac{\lambda_d}{d}}^2, $$
by using that $ \delta \mid d_1 $ and $ \delta \mid d_2 $ if and only if $ \delta \mid d_1d_2 / \br{d_1, d_2} $. Set $ u_\delta = \sum_{\delta \mid d, \ d \le R} \lambda_d / d $. Then
$$ Q\br{\overrightarrow{\lambda}} = \sum_{\delta \le R} \Phi\br{\delta}u_\delta^2. $$

\lecture{30}{Wednesday}{12/12/18}

Claim that
\begin{equation}
\label{eq:8}
\dfrac{\lambda_d}{d} = \sum_{d \mid \delta, \ \delta \le R} \mu\br{\dfrac{\delta}{d}}u_\delta.
\end{equation}
The right hand side is
$$ \sum_{d \mid \delta, \ d \le R} \mu\br{\dfrac{\delta}{d}}\br{\sum_{\delta \mid d', \ d' \le R} \dfrac{\lambda_{d'}}{d'}} = \sum_{d' \le R} \dfrac{\lambda_{d'}}{d'}\br{\sum_{d \mid \delta \mid d'} \mu\br{\dfrac{\delta}{d}}}. $$
So we need to show that
$$ \sum_{d \mid \delta \mid d'} \mu\br{\dfrac{\delta}{d}} =
\begin{cases}
1 & d = d' \\
0 & \text{otherwise}
\end{cases}.
$$

\pagebreak

The sum is equal to
$$ \sum_{m \mid d' / d} \mu\br{m} = \br{1 * \mu}\br{\dfrac{d'}{d}} = \epsilon\br{\dfrac{d'}{d}}. $$
The condition that $ \lambda_1 = 1 $ translates via $ \br{\ref{eq:8}} $ to the condition that $ 1 = \sum_{\delta \le R} \mu\br{\delta}u_\delta $. The Cauchy-Schwarz inequality is $ \abs{ab} \le \abs{a}\abs{b} $, that is
$$ \sum_i a_ib_i \le \br{\sum_i a_i^2}^{\tfrac{1}{2}}\br{\sum_i b_i^2}^{\tfrac{1}{2}}, $$
with equality if and only if there exists $ \lambda $ such that $ b_i = \lambda a_i $ for all $ i $. So
$$ 1 = \sum_{\delta \le R} \mu\br{\delta}u_\delta \le \br{\sum_{\delta \le R}\Phi\br{\delta}u_\delta^2}^{\tfrac{1}{2}}\br{\sum_{\delta \le R}\dfrac{\mu\br{\delta}^2}{\Phi\br{\delta}}}^{\tfrac{1}{2}}. $$
So
$$ Q\br{\overrightarrow{\lambda}} = \sum_{\delta \le R} \Phi\br{\delta}u_\delta^2 \ge \dfrac{1}{D}, \qquad D = \sum_{\delta \le R} \dfrac{\mu\br{\delta}^2}{\Phi\br{\delta}}. $$
Equality holds when $ u_\delta = \mu\br{\delta} / D\Phi\br{\delta} $. We are going to show that $ D \ge \log R + \O\br{1} $. Since $ R = Y^c $, this gives us a leading term of
$$ \dfrac{Y}{\log R} = \dfrac{Y}{\log Y^c} = \dfrac{1}{c}\br{\dfrac{Y}{\log Y}}. $$
$ c < \tfrac{1}{2} $ implies that $ 1 / c > 2 $, so
$$ D = \sum_{\delta \le R} \dfrac{\mu\br{\delta}^2}{\Phi\br{\delta}} = \sum_{\delta \le R, \ \delta \ \text{squarefree}} \dfrac{1}{\Phi\br{\delta}}. $$
If $ \delta $ is squarefree, write $ \delta = p_1 \dots p_k $. Then
$$ \Phi\br{\delta} = \br{p_1 - 1} \dots \br{p_k - 1} = p_1 \dots p_k\br{1 - \dfrac{1}{p_1}} \dots \br{1 - \dfrac{1}{p_k}}. $$
So
$$ D = \sum_{\delta \le R, \ \delta \ \text{squarefree}} \dfrac{1}{\delta}\prod_{p \mid \delta} \br{1 - \dfrac{1}{p}}^{-1}. $$
Now, $ \br{1 - 1 / p}^{-1} = 1 + 1 / p + \dots $. So
$$ D = \sum_{\delta \le R, \ \delta \ \text{squarefree}} \dfrac{1}{\delta}\prod_{p \mid \delta} \br{1 + \dfrac{1}{p} + \dots} \ge \sum_{n \le R} \dfrac{1}{n} = \log R + \O\br{1}, $$
by taking $ n \le R $, and writing $ n = p_1^{a_1} \dots p_m^{a_m} $ and $ \delta = p_1 \dots p_m \le R $ squarefree, so
$$ \dfrac{1}{n} = \dfrac{1}{\delta}\br{\dfrac{1}{p_1^{a_1 - 1}} \dots \dfrac{1}{p_m^{a_m - 1}}}. $$
The only thing remaining is to show that $ \lambda_d \ll_\epsilon d^\epsilon $. Recall that $ u_\delta = \mu\br{\delta} / D\Phi\br{\delta} $. So
$$ \lambda_d = d\sum_{d \mid \delta, \ \delta \le R} \mu\br{\dfrac{\delta}{d}}u_\delta = \dfrac{d}{D}\sum_{d \mid \delta, \ \delta \le R} \dfrac{\mu\br{\tfrac{\delta}{d}}\mu\br{\delta}}{\Phi\br{\delta}} = \dfrac{d}{D}\sum_{d \mid \delta, \ \delta \le R, \ \delta \ \text{squarefree}} \dfrac{\mu\br{\tfrac{\delta}{d}}\mu\br{\delta}}{\Phi\br{\delta}}. $$
Write $ \delta' = \delta / d $. Since $ \delta = \delta'd $, and $ \delta $ is squarefree, we have $ \br{\delta', d} = 1 $, so $ \Phi\br{\delta} = \Phi\br{\delta'}\Phi\br{d} $. So
$$ \abs{\lambda_d} \le \dfrac{d}{\Phi\br{d}D}\sum_{\delta' \le R, \ \delta' \ \text{squarefree}} \dfrac{1}{\Phi\br{\delta'}} = \dfrac{d}{\Phi\br{d}}. $$
Need to show that $ \Phi\br{d} \gg_\epsilon d^{1 - \epsilon} $ if $ d $ is squarefree, where $ \Phi\br{d} = \prod_{p \mid d} \br{p - 1} $. If $ p $ is sufficiently large, then $ p - 1 \ge p^{1 - \epsilon} $. If $ p $ is not sufficiently large, then $ \br{p - 1} / p > 0 $ can be regarded as a constant.
\end{proof}

\end{document}