## Prime residues

If n and a are coprime integers then there are infinitely many primes equal to a mod n. This is usually referred to as Dirichlet’s theorem, a result in analytic number theory. For certain combinations of n and a there also exist “elementary” proofs. In this post we will give proofs for any odd n and $a = \pm 1$ and indicate how a proof can be obtained for other specific cases. These results go at least as far back as Issai Schur. Let’s start with

For any positive integer n there are infinitely many primes 1 mod n.

If a prime p does not divide n and q is a power of p then $X^n-1$ does not have double roots in the field $\mathbb{F}_q$. This follows from the relation $n X^{n-1} X - n(X^n-1) = n$ since for a double root $\alpha$ both $n \alpha^{n-1}$ and $\alpha^n-1$ are zero. The polynomial $X^n-1$ factors as a product of cyclotomic polynomials

$X^n-1 = \displaystyle \prod_{d | n} \Phi_d(X).$

In particular the minimal polynomial for a primitive n-th root of unity is the cyclotomic polynomial $\Phi_n(X) \in \mathbb{Z}[X]$.  If a prime p coprime to n divides $\Phi_n(m)$ for some $m \in \mathbb{Z}$ then $\Phi_n$ has a root in $\mathbb{F}_p$ and this must be a primitive n-th root of unity since $X^n-1$ has no double roots in $\mathbb{F}_p$. The multiplicative order of any element in $\mathbb{F}_p^{\ast}$ must divide $|\mathbb{F}_p^{\ast}| = p-1$ so in particular $n | p-1$. This shows that p is 1 mod n. Now an infinite number of primes appear as a divisor of some number in $\{ \Phi_n(m) \;|\; m \in \mathbb{Z} \}$. This follows for example from an Euclid type of argument. Since only a finite number of these primes can divide n there are an infinite number equal to 1 mod n. The elementary argument for prime residue -1 is less known. I will sketch a proof that paves our way for other residues as well.

For any integer n > 2 there are infinitely many primes equal to -1 mod n.

Let $\zeta$ be a primitive n-th root of unity in a field F and factor the cyclotomic polynomial $\Phi_n$ as follows

$\Phi_n(X) = \displaystyle \prod_k (X - \zeta^k)(X-\zeta^{-k}) = \prod_k (X^2-(\zeta^k + \zeta^{-k})X+1)$

where the product is taken over all $1 \leq k < n/2$ that are coprime with n (so a total of $\phi(n)/2$ quadratic factors). Because $X^n-1$ has no double roots in F all these factors are distinct. If m is coprime with n then the field automorphism that maps $\zeta$ to $\zeta^m$ permutes these factors. This permutation fixes a factor exactly when m is $\pm 1$ mod n (in which case it fixes all factors). If F is $\mathbb{F}_q$ for some prime power $q = p^d$ then the Frobenius automorphism $x \mapsto x^p$ fixes a factor exactly if $\zeta + \zeta^{-1} \in \mathbb{F}_p$. Combining these observations shows that the property $p = \pm 1$ mod n is equivalent to $\zeta + \zeta^{-1} \in \mathbb{F}_p$ for any prime p coprime to n. Let $P \in \mathbb{Z}[X]$ be the minimal polynomial of $\zeta + \zeta^{-1}$ over $\mathbb{Q}$. If a prime p is coprime to n and divides $P(m)$ for some integer m then $P$ has a root in $\mathbb{F}_p$ and so $p = \pm 1$ mod n. This almost completes the proof. Again there are infinitely many primes that divide some value $P(m)$ but now we also have to know that infinitely many of those are -1 mod n. In this case that can be concluded (with some effort) from the fact that $P$ has both positive and negative values on $\mathbb{Q}$ since all its roots are real.

Let’s try this for n=5. Then $P(X) = X^2 + X - 1$ and starting at m=1 the first ten values $P(m)$ are

$1, 5, 11, 19, 29, 41, 5 \times 11, 71, 89, 109$

and 19, 29, 89 and 109 are all -1 mod 5. This argument for residue -1 was taken a bit further by Issai Schur and I will conclude with only a hint of his work.

Let n be a positive integer and $\mathbb{Z}_n^{\ast}$ the group of invertible numbers mod n. Let $G \subset \mathbb{Z}_n^{\ast}$ be a subgroup and $H = \mathbb{Z}_n^{\ast}/G$. Let

$f(X) = \displaystyle \prod_{m \in G} (X - \zeta^m) = c_0 + c_1X + \dotsc + X^{|G|}$

and let $\alpha$ be a generator such that $\mathbb{Q}(c_0, c_1, \dotsc, c_{|G|-1}) = \mathbb{Q}(\alpha)$. For $h \in H$ let $\sigma_h$ be a field automorphism that maps $\zeta$ to $\zeta^m$ for some m in the coset h. Then the cyclotomic polynomial $\Phi_n$ can be factored as

$\Phi_n(X) = \displaystyle \prod_{h \in H} \sigma_h f(X)$

and all factors are distinct. The Frobenius automorphism of $\mathbb{F}_q$ where $q = p^d$ fixes a (all) factors exactly if the residue class of p is an element of G. This happens (except for some finite number of primes) exactly when the minimal polynomial $P \in \mathbb{Z}[X]$ of $\alpha$ has a root in $\mathbb{F}_p$. In particular if $b^2 \equiv 1$ mod n and $G = \langle b \rangle$ then this procedure produces a polynomial $P$ such that any prime divisor p of $P(m)$ is equal to 1 or b mod n with only a finite number of exceptions. However, in general there is no easy way to see that there must be inifinitely many primes with residue b. Nevertheless in particular cases this can often be seen. As an example take n=8 and b=3. Then

$\Phi_8(X) = (X^2-\sqrt{-2}X - 1)(X^2+\sqrt{-2}X-1)$

and the minimal polynomial of $\sqrt{-2}$ is $X^2+2$. Starting at m=1 the first ten values $P(m)$ are

$3, 2 \times 3, 11, 2 \times 3^2, 3^3, 2 \times 19, 3 \times 17, 2 \times 3 \times 11, 83, 2 \times 3 \times 17$

and 3, 11, 19 and 83 are 3 mod 8. In this case the only “exceptional” prime is 2 which is a divisor of 8.