[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).[/step]

[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: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][/step]

[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: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.[/step]

[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: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.[/step]

[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]