# For what subsets S of (Z/nZ)* is there a Euclidean proof that there are infinitely many primes whose residues lie in S?

For small values of $n$ and $(a, n) = 1$ it is sometimes possible to give an elementary proof that there are infinitely many primes congruent to $a \bmod n$ along the lines of Euclid's classic proof of the infinitude of the primes. The idea is to find a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $a \bmod n$ or $1 \bmod n$, and such that the first case occurs infinitely many times; then one proves, just as Euclid did, that the integer values of $p$ are divisible by infinitely many primes, and then one contrives to avoid the residue $1 \bmod n$ (if $a \neq 1$; if $a = 1$ then we take $p(t) = \Phi_n(t)$.) Results of Schur and Murty (see this paper of Keith Conrad) then imply that such a polynomial $p$ exists if and only if $a^2 \equiv 1 \bmod n$.

Say that a subset $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ has property E if there exists a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $s \bmod n$ or $1 \bmod n$ for some $s \in S$, and such that the first case occurs infinitely many times. Then we know that any $S$ containing an element squaring to $1$ has property E.

However, there exist subsets $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ not containing such an element with property E. For example, let $G$ be a proper subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$, let $a \not \in G$, and consider

$$p(t) = nt + a.$$

Any prime divisor of $n + a$ is relatively prime to $a$, and at least one of these prime divisors must have residue $\bmod n$ not in $G$. If $p_1, ... p_k$ are finitely many such primes, then $p(p_1 ... p_k) \equiv a \bmod n$ and hence must have a prime factor with the same property which moreover is relatively prime to each $p_i$. It follows that $S = (\mathbb{Z}/n\mathbb{Z})^{\ast} - G$ has property E, and if $n$ does not divide $24$, then taking $G$ to be the subgroup of square roots of $1$ gives the desired example.

Question: What subsets $S$ of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$ have property E and are minimal under inclusion? Are they closed under non-empty intersection?

(If this question is somehow answered in Conrad's paper, my apologies; the material is somewhat beyond me.)

-
Please give an example or two of such subsets S, to improve the context of the question. –  KConrad Dec 24 '10 at 15:06
This does not directly answer your question, but in Granville's paper ams.org/mathscinet-getitem?mr=1220462 elementary methods are used to show that the primes mod n are equidistributed either in all of $(Z/NZ)^*$ or in the complement of an index 2 multiplicative subgroup containing the squares, and that this is in some sense the "limit" of elementary methods. This suggests (but does not prove) that for your question, S cannot be contained in any index 2 multiplicative subgroup of $(Z/NZ)^*$. –  Terry Tao Dec 24 '10 at 18:33
There are a couple of reasons. The first is pedagogical: it's nice to know how much of Dirichlet's theorem you can prove to a group of bright high school students without (perhaps I should say before) introducing analysis. The second is that I am interested in the "limit" of elementary methods so I can better appreciate exactly what I am gaining from using analysis. –  Qiaochu Yuan Dec 25 '10 at 6:19
Qiaochu: what you're gaining from analysis is the full theorem. I wouldn't consider the high school methods as doing anything for you but giving some special cases, which do provide a nice illustration of some special cases of quadratic reciprocity (e.g., knowing when -1 mod p is a square or when 2 mod p is a square can be used to prove special cases of Dirichlet's theorem mod 4 or mod 8) but not much of value beyond that I think. –  KConrad Dec 25 '10 at 15:08
There was a great deal of excitement at the time when Erdos and Selberg came up with an elementary (i.e., not using complex analysis) proof of the prime number theorem. The hope, of course, was that the new proof would provide new insights, and maybe even give better error estimates. Similarly, I think there would be significant interest in an elementary proof of the general form of Dirichlet's theorem. Of course, elementary does not mean easy, or suitable for teaching to high school students. I agree that for teaching, the analytic proofs are best. –  Joe Silverman Jan 13 '11 at 18:16

I will try to convince you that no Euclidean proof can possibly show that there are infinitely many primes which are $2 \mod 5$. After giving some definitions, I will explain what I will actually show:

Let $G$ be a finite group. We define an equivalence relation on $G$ by $g \sim h$ if the (cyclic) subgroups generated by $g$ and by $h$ are conjugate. The equivalence classes for this relation are called divisions. Observe that a map of groups always respects this equivalence relation. A more precise (but not yet precise) claim is:

Consider any Euclidean proof that there are infinitely many primes in some subset $S$ of $\mathbb{Z}/N^*$. Then the set $S$ contains a complete division.

Since $\mathbb{Z}/N^*$ is abelian, the conjugacy part of the definition of abelianness doesn't come directly into this theorem, but it will arise in the proof.

So, what is a Euclidean proof? Well, at some step in the proof, I must build a prime $p$ and say "$p$ has the property $P$, and therefore $p$ is in $S$." In every Euclidean proof I have seen, $P$ is one of two things:

(1) There is a number $M$ such that $M$ is not in some subgroup $G$ of $(\mathbb{Z}/N)^*$. So $M$ has a prime divisor which is not in $G$, and we choose $p$ to be that prime factor. So an allowable step in a Euclidean-proof is showing that there are infinitely many primes not in some subgroup $G$ of $(\mathbb{Z}/N)^*$

(2) Some polynomial $f(X)$ factors in a particular way modulo $p$, and therefore $f$ lies in some class modulo $N$. (Generally, the observation is that $f$ has a root modulo $p$, but I'll allow more general things like $f$ has a quadratic factor" as well. For a polynomial $f$ of degree $n$, and a partition $\lambda$ of $n$, let $D(f, \lambda)$ be the set of primes such that the irreducible factors of $f$ have degrees $(\lambda_1 \lambda_2, \ldots, \lambda_r)$. And let $D(f, \lambda, N)$ be the image of $D(f, \lambda)$ modulo $N$. So an allowable step in an Euclidean-proof will be showing that there are infinitely many primes in some union of $D(f, \lambda, N)$'s.

So, what I will actually be proving is

Any subgroup $G$ of $(\mathbb{Z}/N)^*$, and any $D(f, n, \lambda)$ in $(\mathbb{Z}/N)^*$, is a union of divisions.

So, suppose that $S$ is a set which does not contain any division, and let $T$ be disjoint from $S$, but contain an element representing every division class in $S$. If we have a Euclidean proof, it will construct some prime $p$. We may know that $p$ is not in various subgroups of $(\mathbb{Z}/N)^*$, or that $p$ is in some union of $D(f, \lambda, N)$'s. But that information can't distinguish whether $p$ is in $S$ or in $T$, so our proof can't show that $p$ is in $S$.

OK, my last boxed claim is a precise statement. Let's prove it.

It is easy to see that a subgroup of $(\mathbb{Z}/N)^*$ is a union of divisions (since we are in an abelian group, the conjugacy part of the definition is irrelevant). The complement of a subgroup is likewise such a union.

The interesting thing is $D(f, \lambda, N)$. Let $K$ be a Galois field where $f$ and $x^N-1$ both split. Let $G$ be the corresponding Galois group, so $G$ comes equipped with a map to $(\mathbb{Z}/N)^* \cong \mathrm{Gal}(\mathbb{Q}(\zeta_N)/\mathbb{Q})$.

Now, as you probably know, for $p$ a prime unramified in $K$, the factorization of $f$ modulo $p$ is determined by the Frobenius conjugacy class of $p$ in $G$. What you may or may not know is that it is actually determined by the division class of $p$! (For example, $x^5-1$ has the same factorization modulo primes which are $2 \mod 5$ and primes which are $3 \mod 5$.) To see this, just look at the recipe for reading the factorization off from the Frobenius class. It may or may not help to prove the following lemma: If $g \sim h$, and $X$ is a set with a $G$ action, then there is an order preserving bijection between the $g$ and the $h$ orbits in $X$.

So, the possible Frobenius classes in $G$ of primes in $D(f, \lambda)$ are unions of divisions (I am implicitly using the Cebotarov density theorem here). But then $D(f, \lambda, N)$ is just the projection to $(\mathbb{Z}/N)^*$ of the possible Frobenius classes in $G$ of primes in $D(f, \lambda)$. Since maps of groups take divisions to divisions, this shows that $D(f, \lambda, N)$ is a union of divisions.

Frobenius's density Theorem states that there are infinitely many primes with Frobenius in every division. (And, more precisely, that their Dirichlet density is the size of the division divided by the order of $G$.) It is significantly easier than Cebatarov's, using only the material from a first course in algebraic number theory and a first course in analytic number theory.

Cebatarov's density theorem is the "union" of Frobenius's and Dirichlet's theorems. What I am suggesting is that Euclidean methods, at best, can only get at their intersection.

I am not sure whether or not I think Euclidean proofs can get that far. If you think they can, give me a Euclidean proof that there are infinitely many primes which are in $\{ 3, 5 \}$ mod $7$. I can show infinitely many in $\{ 3,5,6 \}$, and infinitely many in $\{ 2,3,4,5 \}$, but I can't get the intersection.

-

This could be helpfull: "Certain other cases of Dirichlet's Theorem have been proved by elementary methods;in fact,elementary proofs have been found for general classes... M Brauer found a rather simple proof that there are infinitely many primes of the form $ak+1$ and $ak-1$ for every positive integer a".Topics in the theory of numbers by Paul Erdos and Janos Suranyi page 178-180.

-
Yes, I am already aware of this; it follows from the result cited at the end of the first paragraph. –  Qiaochu Yuan Jan 13 '11 at 15:38
sorry i havent noticed that.Do you know any other general classes because i am interested on that too. Moreover is there any proof with elementary methods that there is at least one prime of the form ak+m (a,m)=1?(for some general classes etc.) –  asterios gantzounis Jan 13 '11 at 15:47