## Number Theory: Lecture 14

In which we start to explore the distribution of the primes.

• We reminded ourselves of some examples of results that we have previously seen of the form “There are infinitely many primes congruent to a modulo n”, such as when $a = 1$, $n = 4$ and $a = 3$, $n = 4$.
• We noted that if $a$ and $n$ are not coprime, then this result clearly does not hold.
• Theorem 43 (Dirichlet): Let $n$ be an integer greater than 1, and let $a$ be coprime to $n$.  Then there are infinitely many primes congruent to $a$ modulo $n$.  We did not prove this!  But we saw a small hint of how one can prove it.
• Proposition 44: For any $x \geq 10$, we have $\sum_{p \leq x} \frac{1}{p} \geq \log \log x - \frac{1}{2}$, where the sum is over all primes $p \leq x$.  We proved this by first showing that $\prod_{p \leq x} (1-\frac{1}{p})^{-1} \geq \log x$, and then that $\log \left(\prod_{p \leq x} (1 - \frac{1}{p})^{-1} \right) - \sum_{p \leq x} \frac{1}{p}$ is bounded above by a constant (1/2, as it happens).
• Corollary 45: There are infinitely many primes.
• Proposition 46: There is a constant $c > 0$ such that $\pi(x) \geq c \log x$.  We proved this using an idea of Erdős, namely to write each $y \leq x$ as $y = m^2 p_1^{\alpha_1} \dotsm p_k^{\alpha_k}$, where the $p_i$ are the primes up to $x$ and each $\alpha_i$ is 0 or 1, and then to count the number of such expressions.

Wikipedia has a page with a couple of ways of thinking about $\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!)
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 ... 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 $\sum_{d|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 $\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.