## 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).

• 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$?