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.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s