## Number Theory: Lecture 13

In which we characterise sums of two squares.

• Proposition 39 (Hensel’s Lemma): Let $f$ be a polynomial with integer coefficients, and let $p$ be a prime. Suppose that there is some $x_1$ such that $f(x_1) \equiv 0 \pmod{p}$ and $f'(x_1)\not\equiv 0 \pmod{p}$.  Then for each positive integer $r$ there is some $x_r$ such that $f(x_r) \equiv 0 \pmod{p^r}$.  This is reminiscent of Newton’s method.  We proved it by induction on $r$, arguing that if we had a suitable $x_{r-1}$, then we could choose some $\lambda$ such that $x_r = x_{r-1} + \lambda p^{r-1}$ would work.
• 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 has no prime factor congruent to 3 modulo 4.  We showed that there is a unique reduced form of discriminant $-4$, namely $(1,0,1)$.  So, by Theorem 38 from last time, $n$ can be properly represented by $x^2 + y^2$ if and only if there is a solution to the congruence $w^2 \equiv -4 \pmod{4n}$.  We then used the Chinese Remainder Theorem, Hensel’s lemma (above), and a quick check modulo powers of 2, to reduce this to the condition that $-1$ must be a quadratic residue modulo each odd prime dividing $n$, and also $n$ must not be divisible by 4.
• Corollary 41: The natural number $n$ can be written as the sum of two squares if and only if each prime congruent to 3 modulo 4 in the prime factorisation of $n$ occurs to an even power.  Once we have the theorem above, this follows immediately by multiplying through by a square.
• Theorem 42 (Lagrange): Every natural number is a sum of four squares.  We are not going to prove this result in this course (although it’s not a terribly difficult theorem to prove).

#### Further reading

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.

#### Preparation for Lecture 14

We’re about to move on to a new topic: the distribution of the primes.  Here are some questions to consider.

• Show (if you haven’t done so previously) that there are infinitely many primes congruent to 1 modulo 4, and that there are infinitely many primes congruent to 3 modulo 4.  What conditions would you need to put on $a$ and $n$ to ensure that there are infinitely many primes congruent to $a$ modulo $n$?
• You hopefully know that $\sum_n \frac{1}{n}$ diverges, but that $\sum_n \frac{1}{n^2}$ converges.  What about $\sum_p \frac{1}{p}$ (where the sum is over all primes $p$)?  Can you estimate $\sum_{p \leq x} \frac{1}{p}$ as a function of $x$?
Advertisements