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 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 does not have double roots in the field . This follows from the relation since for a double root both and are zero. The polynomial factors as a product of cyclotomic polynomials

In particular the minimal polynomial for a primitive n-th root of unity is the cyclotomic polynomial . If a prime p coprime to n divides for some then has a root in and this must be a primitive n-th root of unity since has no double roots in . The multiplicative order of any element in must divide so in particular . This shows that p is 1 mod n. Now an infinite number of primes appear as a divisor of some number in . 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 be a primitive n-th root of unity in a field F and factor the cyclotomic polynomial as follows

where the product is taken over all that are coprime with n (so a total of quadratic factors). Because has no double roots in F all these factors are distinct. If m is coprime with n then the field automorphism that maps to permutes these factors. This permutation fixes a factor exactly when m is mod n (in which case it fixes all factors). If F is for some prime power then the Frobenius automorphism fixes a factor exactly if . Combining these observations shows that the property mod n is equivalent to for any prime p coprime to n. Let be the minimal polynomial of over . If a prime p is coprime to n and divides for some integer m then has a root in and so mod n. This almost completes the proof. Again there are infinitely many primes that divide some value 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 has both positive and negative values on since all its roots are real.

Let’s try this for n=5. Then and starting at m=1 the first ten values are

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 the group of invertible numbers mod n. Let be a subgroup and . Let

and let be a generator such that . For let be a field automorphism that maps to for some m in the coset h. Then the cyclotomic polynomial can be factored as

and all factors are distinct. The Frobenius automorphism of where 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 of has a root in . In particular if mod n and then this procedure produces a polynomial such that any prime divisor p of 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

and the minimal polynomial of is . Starting at m=1 the first ten values are

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.