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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: