## Number Theory: Lecture 13

In which we think about which numbers are represented by the forms $x^2 + y^2$ and $x^2 + xy + y^2$ (amongst others).

• Theorem 38: Let $n$ be a natural number.

1. Suppose that $n$ is properly represented by a form of discriminant $d$.  Then there is a solution to the congruence $w^2 \equiv d \pmod{4n}$.
2. Suppose that there is a solution to the congruence $w^2 \equiv d \pmod{4n}$.  Then there is a form of discriminant $d$ that properly represents $n$.

We proved this with the help of Lemma 37.

• Proposition 39 (Hensel‘s Lemma): Let $f$ be a polynomial with integer coefficients, and let $p$ be an odd prime.  Suppose that there is an integer $x_1$ such that $f(x_1) \equiv 0 \pmod{p}$ and $f'(x_1) \not\equiv 0 \pmod{p}$.  Then for each $r \geq 1$ there is some $x_r$ such that $f(x_r) \equiv 0 \pmod{p^r}$.  We proved this inductively, showing that for each $r$ there is an $x_r$ such that $f(x_r) \equiv 0 \pmod{p^r}$ and $x_r \equiv x_1 \pmod{p}$ (so $f'(x_r) \not\equiv 0 \pmod{p}$).

#### Understanding today’s lecture

Pick a form $f$.  Can you find a necessary and sufficient condition for $f$ to represent a prime $p$?  (How does the class number of the discriminant of $f$ make a difference?)

I mentioned that Hensel’s Lemma is reminiscent of Newton’s method.

Jones and Jones (Elementary number theory) has another explicit example of an application of Hensel’s lemma.

#### Preparation for Lecture 14

Can you finish classifying the numbers that can be written as a sum of two squares?

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