[proofplan]
Column orthogonality of Dirichlet characters modulo $q$ isolates the primes $p \equiv a \pmod q$ inside the sum $\sum_p p^{-s}$: the quantity $\sum_{p \equiv a} p^{-s}$ equals $\frac{1}{\varphi(q)} \sum_i \overline{\chi_i(a)} \sum_p \chi_i(p) p^{-s}$, where $\chi_1, \ldots, \chi_{\varphi(q)}$ are the Dirichlet characters of modulus $q$. The inner sum $\sum_p \chi(p) p^{-s}$ is the leading term of the logarithmic expansion of the Euler product of $L(\chi, s)$; the tail (multi-prime contributions) is bounded at $s = 1$. We then compute the behaviour of $\log L(\chi_i, s)$ at $s = 1$: for the trivial $\chi_1$, $L(\chi_1, s)$ has a simple pole, so $\log L(\chi_1, s) \to +\infty$ as $s \to 1^+$; for non-trivial $\chi_i$ ($i \geq 2$), $L(\chi_i, 1) \neq 0$ by [Theorem 1624](/theorems/1624), so $\log L(\chi_i, s)$ remains bounded. The single divergent contribution of $\chi_1$ forces $\sum_{p \equiv a} p^{-s}$ to diverge, meaning there must be infinitely many primes in the progression.
[/proofplan]
[step:Apply column orthogonality to isolate the arithmetic progression]
Let $a, q \in \mathbb{N}$ with $\gcd(a, q) = 1$, and let $\chi_1, \ldots, \chi_{\varphi(q)}$ be the Dirichlet characters of modulus $q$ (with $\chi_1$ the trivial character).
[claim:Column Orthogonality]
For $n \in \mathbb{Z}$ with $\gcd(n, q) = 1$,
\begin{align*}
\frac{1}{\varphi(q)} \sum_{i = 1}^{\varphi(q)} \overline{\chi_i(a)} \chi_i(n) &= \begin{cases} 1 & n \equiv a \pmod q, \\ 0 & \text{otherwise}. \end{cases}
\end{align*}
For $n$ with $\gcd(n, q) > 1$, every $\chi_i(n) = 0$, so both sides reduce to $0 = 0$.
[/claim]
[proof]
The sum $\sum_i \overline{\chi_i(a)} \chi_i(n) = \sum_i \chi_i(n a^{-1})$, where $a^{-1}$ denotes the multiplicative inverse of $a$ in $(\mathbb{Z}/q\mathbb{Z})^\times$ and we use $\overline{\chi_i(a)} = \chi_i(a)^{-1} = \chi_i(a^{-1})$ (since $|\chi_i(a)| = 1$ and $\chi_i$ is a group homomorphism). By row orthogonality for the finite abelian group $G = (\mathbb{Z}/q\mathbb{Z})^\times$:
\begin{align*}
\sum_{\chi \in \widehat{G}} \chi(g) &= \begin{cases} |G| = \varphi(q) & g = e, \\ 0 & g \neq e, \end{cases}
\end{align*}
where $\widehat{G}$ is the group of characters of $G$. Applying with $g = n a^{-1} \in G$:
\begin{align*}
\sum_{i = 1}^{\varphi(q)} \chi_i(n a^{-1}) &= \begin{cases} \varphi(q) & n a^{-1} \equiv 1 \pmod q, \\ 0 & \text{otherwise}. \end{cases}
\end{align*}
The condition $na^{-1} \equiv 1 \pmod q$ is equivalent to $n \equiv a \pmod q$. Dividing by $\varphi(q)$ gives the claim.
[/proof]
Applying the claim to the sum $\sum_p \chi(p) p^{-s}$ over primes: for $s > 1$ real (so absolute convergence holds), summing $\frac{1}{\varphi(q)} \sum_i \overline{\chi_i(a)} \chi_i(p)$ over all primes $p$ gives
\begin{align*}
\sum_{\substack{p \text{ prime} \\ p \equiv a \pmod q}} p^{-s} &= \frac{1}{\varphi(q)} \sum_{i = 1}^{\varphi(q)} \overline{\chi_i(a)} \sum_{\substack{p \text{ prime} \\ \gcd(p, q) = 1}} \chi_i(p) p^{-s},
\end{align*}
where we have used that primes $p \mid q$ contribute $0$ to both sides (the right side because $\chi_i(p) = 0$ by definition for $p \mid q$; the left side because there are only finitely many primes dividing $q$, and $\gcd(a, q) = 1$ rules out $p \equiv a \pmod q$ for $p \mid q$ as soon as $p \leq q$ is examined).
[guided]
**Row and column orthogonality.** For a finite abelian group $G$ with character group $\widehat{G}$, two standard orthogonality relations hold:
- *Row orthogonality:* for fixed $\chi \in \widehat{G}$, $\sum_{g \in G} \chi(g) = |G| \mathbb{1}_{\chi = 1}$.
- *Column orthogonality:* for fixed $g \in G$, $\sum_{\chi \in \widehat{G}} \chi(g) = |G| \mathbb{1}_{g = e}$.
Both are consequences of the character table of $G$ being a unitary matrix (up to a scaling factor of $|G|^{1/2}$).
**Isolating $p \equiv a \pmod q$.** The Column Orthogonality claim gives a "delta function" at $n = a$: summing $\overline{\chi_i(a)} \chi_i(n)$ over $i$ gives $\varphi(q)$ if $n \equiv a \pmod q$ and $0$ otherwise. This is the analytic analogue of the indicator function $\mathbb{1}_{n \equiv a \pmod q}$.
**Applying to the prime sum.** Multiplying by $p^{-s}$ and summing over all primes $p$ coprime to $q$:
\begin{align*}
\frac{1}{\varphi(q)} \sum_p \sum_i \overline{\chi_i(a)} \chi_i(p) p^{-s} = \sum_p \mathbb{1}_{p \equiv a \pmod q} p^{-s} = \sum_{p \equiv a \pmod q} p^{-s}.
\end{align*}
Interchanging the order of summation (valid on $\operatorname{Re}(s) > 1$ by absolute convergence):
\begin{align*}
\sum_{p \equiv a \pmod q} p^{-s} = \frac{1}{\varphi(q)} \sum_i \overline{\chi_i(a)} \sum_p \chi_i(p) p^{-s}.
\end{align*}
**Exclusion of primes dividing $q$.** Primes $p \mid q$ are finitely many (at most $\log_2 q$), and for each, $\chi_i(p) = 0$ for all $i$ (by definition of Dirichlet characters of modulus $q$). These primes contribute $0$ on the right side.
On the left side, primes $p \mid q$ can only be in the progression $p \equiv a \pmod q$ if $p \mid q$ and $p \equiv a \pmod q$; since $\gcd(a, q) = 1$, such $p$ would have to be coprime to $q$, contradicting $p \mid q$. So the left side's restriction to $p \equiv a \pmod q$ already excludes $p \mid q$.
**Consequence.** If we can show the right side diverges as $s \to 1^+$, then $\sum_{p \equiv a \pmod q} p^{-s} \to \infty$ as $s \to 1^+$, which forces infinitely many primes in the progression (a finite sum of finitely many positive terms would stay bounded).
[/guided]
[/step]
[step:Relate $\sum_p \chi(p) p^{-s}$ to $\log L(\chi, s)$ with bounded error]
[claim:Log Series Identity]
For any Dirichlet character $\chi$ of modulus $q$ and any $s \in \mathbb{C}$ with $\operatorname{Re}(s) > 1$:
\begin{align*}
\log L(\chi, s) &= \sum_p \chi(p) p^{-s} + E_\chi(s),
\end{align*}
where the error term $E_\chi(s) = \sum_p \sum_{n \geq 2} \frac{\chi(p)^n}{n \cdot p^{ns}}$ is bounded uniformly in $s$ on $\{\operatorname{Re}(s) \geq 1\}$:
\begin{align*}
|E_\chi(s)| &\leq \sum_{m \geq 2} \frac{1}{m(m - 1)} = 1,
\end{align*}
independently of $\chi$.
[/claim]
[proof]
For $\operatorname{Re}(s) > 1$, $L(\chi, s) = \prod_p (1 - \chi(p) p^{-s})^{-1}$ is a non-zero convergent Euler product (each factor non-zero because $|\chi(p) p^{-s}| < 1$), so $\log L(\chi, s)$ admits a branch via the standard power series expansion. Expanding $\log(1 - z) = -\sum_{n \geq 1} z^n/n$ for $|z| < 1$:
\begin{align*}
\log L(\chi, s) = -\sum_p \log(1 - \chi(p) p^{-s}) = \sum_p \sum_{n = 1}^\infty \frac{\chi(p)^n}{n \cdot p^{ns}} = \sum_p \frac{\chi(p)}{p^s} + \sum_p \sum_{n = 2}^\infty \frac{\chi(p)^n}{n \cdot p^{ns}}.
\end{align*}
The first term is the main sum $\sum_p \chi(p) p^{-s}$; the second is the error $E_\chi(s)$.
Bounding $E_\chi(s)$: for $\sigma = \operatorname{Re}(s) \geq 1$,
\begin{align*}
|E_\chi(s)| &\leq \sum_p \sum_{n = 2}^\infty \frac{|\chi(p)|^n}{n \cdot p^{n\sigma}} \leq \sum_p \sum_{n = 2}^\infty \frac{1}{p^{n\sigma}} = \sum_p \frac{p^{-2\sigma}}{1 - p^{-\sigma}} \leq \sum_p \frac{1}{p^\sigma(p^\sigma - 1)}.
\end{align*}
Bounding further by extending the sum to all integers $m \geq 2$:
\begin{align*}
\sum_p \frac{1}{p^\sigma(p^\sigma - 1)} &\leq \sum_{m = 2}^\infty \frac{1}{m^\sigma(m^\sigma - 1)} \leq \sum_{m = 2}^\infty \frac{1}{m(m - 1)},
\end{align*}
where the last inequality uses $m^\sigma \geq m$ for $\sigma \geq 1$. The series $\sum_{m \geq 2} \frac{1}{m(m-1)}$ telescopes: $\frac{1}{m(m-1)} = \frac{1}{m - 1} - \frac{1}{m}$, so
\begin{align*}
\sum_{m = 2}^\infty \frac{1}{m(m - 1)} = \sum_{m = 2}^\infty \Bigl(\frac{1}{m - 1} - \frac{1}{m}\Bigr) = 1.
\end{align*}
Therefore $|E_\chi(s)| \leq 1$ for $\operatorname{Re}(s) \geq 1$.
[/proof]
[guided]
**Expanding $\log L(\chi, s)$.** The Euler product $L(\chi, s) = \prod_p (1 - \chi(p) p^{-s})^{-1}$ converges absolutely on $\operatorname{Re}(s) > 1$, and each factor is a non-zero complex number. Taking logarithms (with the principal branch):
\begin{align*}
\log L(\chi, s) = -\sum_p \log(1 - \chi(p) p^{-s}).
\end{align*}
The series $-\log(1 - z) = \sum_{n = 1}^\infty z^n / n$ converges for $|z| < 1$; applied with $z = \chi(p) p^{-s}$:
\begin{align*}
\log L(\chi, s) = \sum_p \sum_{n = 1}^\infty \frac{\chi(p)^n}{n p^{ns}}.
\end{align*}
**Splitting the tail.** The $n = 1$ term is $\sum_p \chi(p)/p^s$, the primary sum of interest. The tail $\sum_{n \geq 2}$ is the error $E_\chi$.
**Bounding $|E_\chi(s)|$ by summation.** Each term satisfies $|\chi(p)^n/(n p^{ns})| \leq 1/p^{n\sigma}$ (using $|\chi(p)| \leq 1$ and $n \geq 1$). Summing:
\begin{align*}
|E_\chi(s)| \leq \sum_p \sum_{n = 2}^\infty p^{-n\sigma} = \sum_p \frac{p^{-2\sigma}}{1 - p^{-\sigma}} = \sum_p \frac{1}{p^\sigma(p^\sigma - 1)}.
\end{align*}
**Dominating by a convergent series.** For $\sigma \geq 1$, $p^\sigma - 1 \geq p - 1 \geq 1$ (for $p \geq 2$), so the summand is at most $1/p^\sigma$. Weaker bound: $\sum_p 1/(p^\sigma(p^\sigma - 1)) \leq \sum_{m \geq 2} 1/(m(m-1)) = 1$ by telescoping.
**Uniform bound.** The bound is independent of $\chi$ and of $s$ (as long as $\sigma \geq 1$), so $|E_\chi(s)| \leq 1$ uniformly.
**Consequence.** As $s \to 1^+$, the error $E_\chi(s)$ remains bounded, and the behaviour of $\sum_p \chi(p)/p^s$ is controlled by $\log L(\chi, s)$ up to a bounded term.
[/guided]
[/step]
[step:Analyse $\log L(\chi_i, s)$ as $s \to 1^+$ for each character]
By Step 2, uniformly in $i$:
\begin{align*}
\sum_p \chi_i(p) p^{-s} &= \log L(\chi_i, s) + O(1) \qquad \text{as } s \to 1^+.
\end{align*}
We analyse each $\log L(\chi_i, s)$ individually.
*Case $i = 1$ (trivial character).* By Step 3 of [Non-Vanishing at $s = 1$](/theorems/1624):
\begin{align*}
L(\chi_1, s) &= \zeta_\mathbb{Q}(s) \prod_{p \mid q} (1 - p^{-s}).
\end{align*}
The factor $\zeta_\mathbb{Q}(s)$ has a simple pole at $s = 1$: $\zeta_\mathbb{Q}(s) = (s - 1)^{-1}(1 + O(s - 1))$ near $s = 1$. The factor $\prod_{p \mid q}(1 - p^{-s})$ is continuous at $s = 1$ with value $\prod_{p \mid q}(1 - 1/p) = \varphi(q)/q > 0$. Therefore for $s \in (1, 2]$ real:
\begin{align*}
L(\chi_1, s) &= \frac{1}{s - 1} \cdot \frac{\varphi(q)}{q} + O(1) \qquad \text{(meaning bounded error as } s \to 1^+).
\end{align*}
More precisely, $L(\chi_1, s) \sim \frac{\varphi(q)/q}{s - 1}$ as $s \to 1^+$, so
\begin{align*}
\log L(\chi_1, s) &= \log\Bigl(\frac{1}{s - 1}\Bigr) + O(1) \to +\infty \qquad \text{as } s \to 1^+.
\end{align*}
*Case $i \geq 2$ (non-trivial character).* By [Non-Vanishing at $s = 1$](/theorems/1624): the hypothesis that $\chi_i$ is non-trivial is satisfied, and the conclusion gives $L(\chi_i, 1) \neq 0$. Combined with [Holomorphicity of Non-Trivial $L$-Functions](/theorems/1620) (which gives that $L(\chi_i, s)$ is holomorphic on $\{\operatorname{Re}(s) > 0\}$, hence continuous at $s = 1$): $L(\chi_i, s)$ is a continuous non-zero function on some neighbourhood of $s = 1$. Therefore
\begin{align*}
\log L(\chi_i, s) &= O(1) \qquad \text{as } s \to 1^+.
\end{align*}
The implied constant depends on the distance from $L(\chi_i, 1)$ to $0$, but since this distance is strictly positive, the constant is finite.
[guided]
**Asymptotics of $\log L(\chi_1, s)$.** The trivial character's $L$-function has a simple pole at $s = 1$:
\begin{align*}
L(\chi_1, s) = \zeta_\mathbb{Q}(s) \cdot \underbrace{\prod_{p \mid q}(1 - p^{-s})}_{\to \varphi(q)/q \text{ as } s \to 1}.
\end{align*}
As $s \to 1^+$, $\zeta_\mathbb{Q}(s) \to \infty$ like $1/(s-1)$, and the prefactor $\prod_{p \mid q}(1 - p^{-s}) \to \varphi(q)/q$, a positive constant. Hence $L(\chi_1, s) \to +\infty$, and $\log L(\chi_1, s) \to +\infty$.
Writing $L(\chi_1, s) = (s-1)^{-1} \cdot (\varphi(q)/q + O(s-1))$ and taking logs:
\begin{align*}
\log L(\chi_1, s) = -\log(s-1) + \log(\varphi(q)/q) + O(s-1) = \log\frac{1}{s-1} + O(1).
\end{align*}
As $s \to 1^+$, $\log\frac{1}{s-1} \to +\infty$.
**Asymptotics of $\log L(\chi_i, s)$ for $i \geq 2$.** The hypothesis of [Theorem 1624](/theorems/1624) (that $\chi_i$ is non-trivial) is satisfied; the conclusion gives $L(\chi_i, 1) \neq 0$. Moreover [Theorem 1620](/theorems/1620) guarantees $L(\chi_i, s)$ is holomorphic (in particular continuous) on $\{\operatorname{Re}(s) > 0\}$, so the function $s \mapsto L(\chi_i, s)$ is continuous and non-zero at $s = 1$. A continuous non-zero function is bounded away from zero on a compact neighbourhood of $s = 1$, so $|L(\chi_i, s)|$ is bounded below and above by positive constants near $s = 1$, which gives $\log|L(\chi_i, s)| = O(1)$.
For $\log L(\chi_i, s)$ (which is generally complex-valued), the same reasoning applies: on a small neighbourhood of $s = 1$ where $L(\chi_i, s) \neq 0$, $\log L(\chi_i, s)$ (chosen continuously) is bounded.
[/guided]
[/step]
[step:Combine the asymptotics to conclude divergence]
From Steps 1, 2, and 3, as $s \to 1^+$ (real):
\begin{align*}
\varphi(q) \sum_{p \equiv a \pmod q} p^{-s} &= \sum_{i = 1}^{\varphi(q)} \overline{\chi_i(a)} \sum_p \chi_i(p) p^{-s} \\
&= \sum_{i = 1}^{\varphi(q)} \overline{\chi_i(a)} \bigl(\log L(\chi_i, s) + O(1)\bigr) \\
&= \overline{\chi_1(a)} \log L(\chi_1, s) + \sum_{i = 2}^{\varphi(q)} \overline{\chi_i(a)} \log L(\chi_i, s) + O(1).
\end{align*}
For $i = 1$: $\chi_1(a) = 1$ (since $\gcd(a, q) = 1$), so $\overline{\chi_1(a)} = 1$, and by Step 3, $\log L(\chi_1, s) \to +\infty$.
For $i \geq 2$: each $\log L(\chi_i, s) = O(1)$ by Step 3, and $|\overline{\chi_i(a)}| \leq 1$, so each term is $O(1)$.
Summing the bounded contributions gives
\begin{align*}
\varphi(q) \sum_{p \equiv a \pmod q} p^{-s} &= \log L(\chi_1, s) + O(1) \to +\infty \qquad \text{as } s \to 1^+.
\end{align*}
In particular, $\sum_{p \equiv a \pmod q} p^{-s} \to +\infty$ as $s \to 1^+$.
Now suppose for contradiction that the arithmetic progression $\{a, a + q, a + 2q, \ldots\}$ contains only finitely many primes $p_1, \ldots, p_N$. Then $\sum_{p \equiv a \pmod q} p^{-s} = \sum_{k = 1}^N p_k^{-s}$, a finite sum of continuous functions. At $s = 1$:
\begin{align*}
\lim_{s \to 1^+} \sum_{k = 1}^N p_k^{-s} &= \sum_{k = 1}^N p_k^{-1} < \infty,
\end{align*}
contradicting the divergence to $+\infty$.
Therefore the progression $\{a, a + q, a + 2q, \ldots\}$ contains infinitely many primes.
[guided]
**Combining the estimates.** Multiplying the identity from Step 1 by $\varphi(q)$:
\begin{align*}
\varphi(q)\sum_{p \equiv a} p^{-s} = \sum_i \overline{\chi_i(a)} \sum_p \chi_i(p) p^{-s}.
\end{align*}
Substituting $\sum_p \chi_i(p) p^{-s} = \log L(\chi_i, s) + O(1)$ (Step 2):
\begin{align*}
\varphi(q)\sum_{p \equiv a} p^{-s} = \sum_i \overline{\chi_i(a)} \log L(\chi_i, s) + \sum_i \overline{\chi_i(a)} O(1) = \sum_i \overline{\chi_i(a)} \log L(\chi_i, s) + O(1),
\end{align*}
where the last $O(1)$ absorbs the finite sum of bounded terms (each $|\overline{\chi_i(a)}| \leq 1$, and there are $\varphi(q)$ terms, giving a bounded sum).
**Isolating the divergent term.**
- $i = 1$: $\overline{\chi_1(a)} = 1$ (the trivial character evaluates to $1$ on $a$ since $\gcd(a, q) = 1$). $\log L(\chi_1, s) \to +\infty$.
- $i \geq 2$: $|\overline{\chi_i(a)}| \leq 1$, and $\log L(\chi_i, s) = O(1)$ is bounded. Each term is $O(1)$.
Summing:
\begin{align*}
\varphi(q)\sum_{p \equiv a} p^{-s} = \log L(\chi_1, s) + O(1) \to +\infty.
\end{align*}
**Rules out finitely many primes.** If there were only finitely many primes $p_1, \ldots, p_N$ in the progression, the sum $\sum_{p \equiv a} p^{-s}$ would be a finite sum $p_1^{-s} + \cdots + p_N^{-s}$, which is continuous at $s = 1$ and has finite value $p_1^{-1} + \cdots + p_N^{-1}$. This contradicts divergence to $+\infty$ at $s \to 1^+$.
**Hence infinitely many primes.** The arithmetic progression $\{a + kq : k \geq 0\}$ contains infinitely many primes, as claimed by Dirichlet's theorem.
**Summary of the logical structure.**
1. Column orthogonality expresses $\sum_{p \equiv a} p^{-s}$ as $\frac{1}{\varphi(q)} \sum_i \overline{\chi_i(a)} \sum_p \chi_i(p) p^{-s}$.
2. Log-expansion relates each $\sum_p \chi_i(p) p^{-s}$ to $\log L(\chi_i, s)$ with bounded error.
3. The trivial $L$-function diverges at $s = 1^+$; non-trivial ones stay bounded (by [Theorem 1624](/theorems/1624)'s non-vanishing and [Theorem 1620](/theorems/1620)'s holomorphicity).
4. The only divergent contribution forces infinitely many primes.
[/guided]
[/step]
