## Number Theory: Lecture 14

In which we determine which numbers are the sum of two squares, and start to study the distribution of the primes.

• Theorem 40: The natural number $n$ can be written as the sum of two coprime squares if and only if $n$ is not divisible by $4$ and every odd prime factor of $n$ is congruent to $1$ modulo $4$.  We collected together various bits of work we’ve done over the last couple of lectures to prove this.
• Corollary 41: The natural number $n$ can be written as the sum of two squares if and only if in the prime factorisation of $n$ each prime congruent to $3$ modulo $4$ occurs to an even power.  This followed from Theorem 40, because $n$ can be written as the sum of two squares if and only if it is the product of a square and a number that can be written as the sum of two coprime squares.
• Theorem 42 (Dirichlet‘s theorem on primes in arithmetic progression): Let $n$ be an integer greater than $1$, and let $a$ be a natural number coprime to $n$.  Then there are infinitely many primes congruent to $a$ modulo $n$.  That is, there are infinitely many primes in the arithmetic progression $a$, $a+n$, $a+2n$, $a+3n$, …. We are not going to see a proof of this result in this course (but see below in the Further reading section for places to look).
• Proposition 43: For $x \geq 10$, we have $\displaystyle \sum_{p \leq x} \frac{1}{p} \geq \log\log x - \frac{1}{2}$We considered $\displaystyle \log\left(\prod_{p \leq x} \left(1 + \frac{1}{p} + \frac{1}{p^2} + \dotsb \right) \right)$.
• Corollary 44: There are infinitely many primes.  This was immediate from Proposition 43.
• Proposition 45: There is a constant $c > 0$ such that $\pi(x) > c \log x$We used an idea of Erdős: any $y \leq x$ can be written as $y = m^2 p_1^{\alpha_1} \dotsm p_k^{\alpha_k}$ where $p_1$, …, $p_k$ are the primes up to $x$, each $\alpha_i$ is $0$ or $1$, and $m \leq \sqrt{x}$.  Then we counted.

#### Understanding today’s lecture

Can you finish off our analysis of which numbers are properly represented by the form $x^2 + xy + y^2$?

Jones and Jones (Elementary number theory) has another explicit example of an application of Hensel’s lemma.  They also devote a chapter to questions about sums of squares, including the problems about sums of two squares and sums of four squares (see below).  Davenport (The Higher Arithmetic) presents another way of characterising the numbers that can be written as the sum of two squares, without using the theory of binary quadratic forms.  You might like to read that for another approach.  Baker (A concise introduction to the theory of numbers) follows the approach that we took in lectures, namely studying the sums of two squares via binary quadratic forms.  Both Baker and Davenport move on to discuss the question of which numbers can be written as the sum of four squares, which leads to a rather lovely (and perhaps surprising) theorem of Lagrange.

Wikipedia has a page with a couple of ways of thinking about $\displaystyle \sum_{p\leq x} \frac{1}{p}$.  Hardy and Wright (An introduction to the theory of numbers) tackles this problem and some related results (see section 22.7).  Erdős and Surányi (Topics in the theory of numbers) give a nice presentation of this material.  Davenport (Multiplicative Number Theory) discusses the sum of the reciprocals of the primes, and also gives a proof of Dirichlet’s theorem on primes in arithmetic progressions.  (Note that this is a different book by Davenport, not the one that I’ve recommended in previous posts!)

#### Preparation for Lecture 15

Next time we shall move on to the Riemann zeta function, and how it is related to the distribution of the primes.   I might mention the Möbius $\mu$ function, which is defined on natural numbers.  If $n = p_1 p_2 \dotsm p_k$, where the $p_i$ are distinct primes, then $\mu(n) = (-1)^k$.  If $n$ is not square-free (if it is not the product of distinct primes), then $\mu(n) = 0$.  And, just to be clear, $\mu(1) = 1$. Here are a couple of questions to get you started thinking about this function.

• Is $\mu$ a multiplicative function?
• Can you compute the sums $\displaystyle \sum_{d\mid n} \mu(d)$ for various $n$?  (The sum is over all divisors $d$ of $n$.)
• Can you make any conjectures about the approximate size of the sum $\displaystyle \sum_{n \leq x} \mu(n)$?  You might like to use a computer to help you collect some data, in addition to thinking about the function $\mu$.
• You might like to try to relate $\mu$ and the Euler totient function $\phi$ that we saw earlier in the course.