# Primes in arithmetic progressions

In analytic number theory, a fundamental problem is to understand the distribution of the primes number $\{2,3,5,\cdots\}$. One important result is Dirichelt’s theorem, which  states that for any two positive coprime integers $a$ and $N$, the are infinitely many primes of the form $qN+a$, where $q$ is a non-negative integer.

Theorem.  Let $a$ and $N$ be fixed an integer with $a$ and $N$ coprime (thus $\gcd(a,N)=1$), then there are infinitely many primes $p$ in the arithmetic progression $\{qa+N:q\in\mathbf{N}\}$.

Remark. If $\gcd(a,N)>1$, then there is at most one prime $p$ meeting the condition $latex $p=a$ mod $N$, since such $p$ would be divisible by the $\gcd$. Thus, the necessity of the gcd condition is obvious. ## Group characters We first explain Dirichlet’s innovation, the use of group characters to isolate in a specified congruence class module $N$. Definitoin. Let $G$ be a finite abelian group, the dual group or group of character $\widehat{G}$ of a abelian group $G$ is $\displaystyle\widehat{G}:=\{\text{group homomorphism}\ \chi:G\to\mathbf{C}^\times\}.$ This $\widehat{G}$ is itself an abelian group under the operation on character defined for $g\in G$ by $\displaystyle(\chi_1\cdot\chi_2)(g):=\chi_1(g)\chi_2(g).$ Definition. Let $G$ be a cyclic group of order $n$ with specified generator $g$. Then $\widehat{G}$ is isomorphic to the group of $n$-th roots of unity $\mu_n$. That is, an $n$-th root of unity $\zeta$ gives the character $\chi$ such that $\displaystyle\chi(g^\ell)=\zeta^\ell.$ In particular, $\widehat{G}$ is a cyclic group of order $n$. Proposition. Let $G=A\oplus B$ be a direct sum of finite abelian groups. Then there is a natural isomorphism of the dual groups $\displaystyle \widehat{A}\oplus\widehat{B}\cong\widehat{G}$ by $(\chi_1,\chi_2)\mapsto \chi_1\cdot\chi_2$, where $\chi_1\cdot\chi_2\in \widehat{G}$ is the character defined by $\displaystyle \chi_1\cdot\chi_2((a,b))=\chi_1(a)\chi_2(b).$ Remark. Combining this proposition and the structure theorem for finite abelian groups, we conclude that $\widehat{G}\cong G$ for a finite abelian group$G\$.

Theorem 1. (Dual version of cancellation) For $g$ in a finite ableian group,
$\displaystyle \sum_{\chi\in\widehat{G}}\chi(g)=\begin{cases} |G|& {\rm for}\ g=e,\\ 0& {\rm otherwise}. \end{cases}$

Proof. If $g=e$, then the sum counts the characters in $\widehat{G}$.
One the other hand, given $g\neq e$ in $G$, by previous proposition let $\chi_1$ be in $\widehat{G}$ such that $\chi_1(g)\neq 0$. The map on $\widehat{G}$
$\displaystyle\chi\mapsto \chi_1\cdot\chi$
is a bijection of $\widehat{G}$ to itself.

## Proof of  Dirichlet’s theorem

Definition.  A  Dirichlet character module $N$  is a group homomorphism
$\displaystyle \chi:(\mathbf{Z}/N\mathbf{Z})^\times\to \mathbf{C}^{\times}$
extended by $0$ to all of $\mathbf{Z}/N\mathbf{Z}$, that is by defining $\chi(a)=0$ if $a$ is not invertible modulo $N$. The trivial or principal character $\chi_0$ module $N$ is the character which takes only the value $1$ and $0$.

Remark. This extension by zero allows us to compose $\chi$ with the reduction-mod-$N$ map $\mathbf{Z}\to\mathbf{Z}/N\mathbf{Z}$ and also consider $\chi$ as a function on $\mathbf{Z}$. Even when extended by $0$ the function $\chi$ is still  multiplicative in the sense that
$\displaystyle \chi(mn)=\chi(m)\chi(n).$

Theorem. $\displaystyle\sum_{a\in\mathbf{Z}/N\mathbf{Z}}\chi(a)=\begin{cases} \varphi(N)& {\rm for}\ \chi=\chi_0,\\ 0& {\rm otherwise}, \end{cases}$
where $\varphi$ is the Euler’s totient function

Proof. The proof is easy, by changing variables.

Dirichlet’s  dual trick is to sum over character $\chi$ module $N$ evaluated at fixed $a$ in $(\mathbf{Z}/N\mathbf{Z})^\times$. From Theorem 1 we see that
$\displaystyle\sum_{\chi\ \text{mod}\ N} \chi(a)=\begin{cases} \varphi(N)& \text{for}\ a=1\ \text{mod}\ N,\\ 0& \text{otherwise}. \end{cases}$
We also have for $b$ invertible module $N$,
$\displaystyle \sum_{\chi\ \text{mod}\ N} \chi(a)^{-1}\chi(b)=\sum_{\chi\ \text{mod}\ N} \chi(a^{-1}b)=\begin{cases} \varphi(N)& \text{for}\ a=b\ \text{mod}\ N,\\ 0& \text{otherwise}. \end{cases}$

Definition. (Dirichlet $L$-function)  Given a character $\chi$ module $N$, the corresponding Dirichlet $L$-function is
$\displaystyle L(s,\chi):=\sum_{n=1}^\infty \frac{\chi(n)}{n^s},\quad \mathrm{Re}(s)>1.$
Since we have the multiplicative property $\chi(mn)=\chi(m)\chi(n)$, each $L$-function has an  Euler product expansion
$\displaystyle L(s,\chi)=\prod_{p\ \text{prime}}\frac{1}{1-\chi(p)p^{-s}}.$

The next step is to take logarithm of $L(s,\chi)$ and equate it to the logarithm of the Euler product. This must be done with some care since complex logarithms can be insidious.
As seen from the Euler product, the $L$-function $L(s,\chi)$ does not vanish in the half-plane $\mathrm{Re}(s)>1$, so the half plane being simple connected, the logarithm $\log L(s,\chi)$ is well defined (for instance, $\log L(s,\chi):=\int_{\gamma}\frac{L'(w,\chi)}{L(w,\chi)}\,dw+c$).

However, when taking the logarithm of the Euler product, one can not immediately infer that one arrive at the sum of the logarithm ($\log (zw)$ is not necessarily equal to $\log z+\log w$; they might different by $2\pi i$). Summing the principal logarithm of the factor in the Euler product, and using the branch it holds that
$\displaystyle -\log(1-z)=\sum_{m=1}^\infty \frac{z^m}{m}$
for $|z|<1$, we arrive at the following series
$\displaystyle G(s)=-\sum_{p}\log(1-\chi(p)p^{-s})=\sum_{p\ \text{prime}}\sum_{m\geq 1}\frac{\chi(p)^m}{mp^{ms}}$
which converges for $\mathrm{Re}(s)>1$, uniformly on compact set, as it is dominated by $\sum_{n\ge 1}\frac{1}{n^s}$. And since exponential function behaves better that the logarithm, i.e., it it continuous and $\exp(z+w)=\exp(z)\exp(w)$ always holds, this series is a logarithm of $L(s,\chi)$ (but may not be the principal one); that is, one has
$\displaystyle \exp(G(s))=L(s,\chi),$

We still use $\log (s,\chi)$ to denote this branch of logarithm, then we have
$\displaystyle \log L(s,\chi)=\sum_{p\ \text{prime},m\geq 1}\frac{\chi(p)^m}{mp^{ms}}=\sum_{p\ \text{prime}}\frac{\chi(p)}{p^s}+\sum_{p\ \text{prime},m\geq 2}\frac{\chi(p)^m}{mp^{ms}}.$
The second sum on the right will turn to be subordinate to the first, so we aim our attention at the first sum where $m=1$.

To pick out the primes $p$ with $p=a$ mod $N$, we use the sum over $\chi$ trick to obtain
$\displaystyle \sum_{\chi\ \text{mod}\ N}\chi(a)^{-1}\frac{\chi(p)}{p^s}=\begin{cases} \varphi(N)p^{-s}& \text{for}\ p=a\ \text{mod}\ N,\\ 0&\text{otherwise}. \end{cases}$
Thus
$\displaystyle \sum_{\chi\ \text{mod}\ N} \chi(a)^{-1}L(s,\chi)=\sum_{\chi\ \text{mod}\ N}\chi(a)^{-1}\sum_{p\ \text{prime},m\geq 1}\frac{\chi(p)^m}{mp^{ms}}\\ \quad\quad\quad\quad=\sum_{p=a\ \text{mod}\ N}\frac{\varphi(N)}{p^s}+\sum_{\chi\ \text{mod}\ N}\chi(a)^{-1}\sum_{p\ \text{prime},m\geq 2}\frac{\chi(p)^m}{mp^{ms}}$