21
$\begingroup$

Dirichlet's theorem states that for any coprime $k$ and $m$ there exists infinitely many primes $p$ such that $p \equiv k \pmod m$.

Some special cases of this theorem are easy to prove without any analytic methods. Those cases include, for example, $m=4, k=1$ and $m=4, k=3$.

Both cases could be proved by considering first $t$ prime numbers $p_i \equiv k \pmod m$ and constructing a new number which is proved to have prime divisor $p \equiv k \pmod m$ that is not equal to any $p_i$.

For case $m=4, k=1$ we can consider number $(p_1 p_2 \cdots p_t)^2 + 1$. And for case $m=4, k=3$ number $4p_1 p_2 \cdots p_t + 3$.

Those constructions could also be applied to some other special cases as well.

Are there any other special cases for which there exists a simple non-analytic proof which don't use any of those two constructions?

$\endgroup$
8
  • $\begingroup$ This question of mine and the answer by Bjorn Poonen deals with many special cases - mathoverflow.net/questions/15220/… $\endgroup$ Jul 20, 2010 at 12:16
  • 1
    $\begingroup$ Here is the similar question - mathoverflow.net/questions/16735/… $\endgroup$ Jul 20, 2010 at 12:19
  • $\begingroup$ I also had a related question mathoverflow.net/questions/25956. $\endgroup$ Jul 20, 2010 at 12:40
  • $\begingroup$ Please explain what do you mean by "a simple non-analytic proof". If one of the two mentioned above, then $m$ should involve only 2s and 3s in its prime factorisation. $\endgroup$ Jul 20, 2010 at 12:45
  • $\begingroup$ Actually I want proof that is niether of two mentioned in the question. By "a simple non-analytic proof" I mean a proof that doesn't use any of classical analysis. $\endgroup$
    – falagar
    Jul 20, 2010 at 13:06

3 Answers 3

21
$\begingroup$

There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in this note. The proof gives a (Euclidean) argument that infinitely many primes divide the values of an integer-coefficient polynomial on the integers, and then notes that the prime divisors of the values of the $n$-th cyclotomic polynomial either divide $n$ or have remainder $1$ upon division by $n$. (The proof is well-known; I don't know the originator.) By the way, the note also contains a cute analytic argument for $p\equiv 1 \bmod 4$ giving bounds on the partial sums of the reciprocals of such primes; the argument uses representations via sums of two squares.

Edit: This paper by Murty and Thain discusses obstructions to Euclid-style proofs for various congruence classes. I believe that a proof has been carried out for $p\equiv a\bmod b$ for $(a, b)=1$ for $b= 24$ in the style of Euclid, however.

Here is an open-access paper by Keith Conrad expositing this impossibility theorem and giving some background.

Edit 2: Here is the paper I recalled with the Euclidean proof for $b= 24$; unfortunately it is not open-access. It is JSTOR however so many of you likely have institutional access.

$\endgroup$
3
  • $\begingroup$ Daniel, I am trying to decide whether your approach is "elementary enough" (of course, the cyclotomic polynomials do not belong to "classical analysis" but analytic proofs for $p\equiv1\pmod m$ are simpler as well; the latter ones, in some sense, generalise the above elementary trick for $3\pmod4$). Thanks for the closed- and open-access links. $\endgroup$ Jul 20, 2010 at 13:59
  • $\begingroup$ Hmm...the proof that infinitely many primes divide the image of a polynomial on the integers is essentially Euclidean, which is why I consider this to be elementary; of course I find the analytic proofs in this case preferable as well. You may also enjoy the analytic proof for $p\equiv 1 \bmod 4$ I give in the note as well, which uses some very cute trickery based on representations via sums of squares. $\endgroup$ Jul 20, 2010 at 14:04
  • $\begingroup$ I have enjoyed! But I have already used my vote... :-( $\endgroup$ Jul 20, 2010 at 14:14
9
$\begingroup$

As Daniel has pointed out, there is an elementary proof that for each $n$ there are infinitely many primes $p$ with $p\equiv1 \pmod n$. There is an also an elementary proof that for each $n$ there are infinitely many primes $p$ with $p\equiv-1 \pmod n$. This can be found in Nagell's Introduction to Number Theory section 50 in the second edition.

$\endgroup$
3
$\begingroup$

I found this generalization of the "$3 \pmod{4}$" version while teaching number theory a few years ago.

Let $G$ be a proper subgroup of $(\mathbb{Z}/n)^\times$. Then there are infinitely many primes $p$ such that $[p]\in (\mathbb{Z}/n)^\times$ and $[p]\not\in G$.

Proof: Suppose as usual that there are finitely many, $p_1, p_2, \ldots, p_r$, and find a number $g$ such that $(p_i,g) = 1$ for all $i$ and $[g]\not\in G$. Then the number $N = np_1 p_2 \cdots p_r + g$ has a prime factorization $N = q_1q_2 \cdots q_s$ satisfying

  • $q_i \neq p_j$ for all $i$ and $j$ and
  • since $[N]=[g]\not\in G$, $[q_i]\not\in G$ for at least on $i$.

EDIT 8-29-20

Here is a detailed proof. There's a bit of fun messing around to find the right number $N$.

Theorem. Let $m\in \mathbb{N}$ and let $G\subseteq (\mathbb{Z}/m)^\times$ be a proper subgroup. Then %for each %$\alpha\in (\mathbb{Z}/m)^\times - G$, there are infinitely many primes $p$ such that $[p] \in (\mathbb{Z}/m)^\times - G$.

Proof. Assume to the contrary that there are only finitely such primes, $$ \mathcal{P} = \{ \mbox{all primes $p$ such that $[p] \in (\mathbb{Z}/m)^\times -G$} \} = \{ p_1, p_2, \ldots, p_r\}. $$ Since each $[p_i]\in (\mathbb{Z}/m)^\times$ we have $(p_i,m) = 1$ for $i= 1, 2, \ldots, r$.

Since $G$ is a proper subgroup of $(\mathbb{Z}/m)^\times$, we can find an integer $a$ such that $[a]\in (\mathbb{Z}/m)^\times - G$; again $(a, m) = 1$.

Now we inductively define a sequence of integers $N_k$ for $k = 0, 1, 2, \ldots, r$ with the properties

  • $N_k \equiv a$ mod $m$
  • $(p_i, N_k) = 1$ for $i=1, 2, \ldots, k$.

The construction begins with $ N_0 = mp_1p_2 \cdots p_r + a . $ Once we have $N_k$, we define $$ N_{k+1} = \left\{ \begin{array}{ll} N_k & \mbox{if $(p_{k+1}, N_k) = 1$} \\ \\ N_k + m p_1p_2\cdots p_k & \mbox{if $p_{k+1} | N_k$.} \end{array} \right. $$ Obviously $N_{k+1} \equiv N_k\equiv a$ mod $m$, and $N_{k+1} \equiv N_k$ mod $p_i$ for each $i = 1, 2, \ldots, k$, so that $$ (N_{k+1}, p_i) = (N_k , p_i) = 1 $$ for $i = 1, 2, \ldots, k$. Furthermore, if $p_{k+1}| N_k$, then $p_{k+1}$ cannot divide $N_{k+1}$, lest $p_{k+1}$ divide $m p_1p_2\cdots p_k$, which is impossible. Therefore the construction continues, and ultimately obtain the integer $N_r$.

Now consider its prime factorization $ N_r = q_1q_2 \cdots q_s $. We can say from what we have done that

  • $q_j \neq p_i$ for any $i$ and $j$, so $[q_j] \in G$ for all $j =1, 2, \ldots, s$, and so
  • $[N_r] = [q_1]\cdot [q_2] \cdots [q_s] \in G$, but
  • $[N_r] = [ a] \not\in G$.

This contradiction of the last two lines shows that our assumption that there are only finitely many such primes $p$ such that $[p]\in (\mathbb{Z}/m)^\times - G$ must be wrong, and this completes the proof.

$\endgroup$
6
  • $\begingroup$ I have no doubt it is correct, but I find it hard to follow. Why is it obvious that the conditions on $g$ can be fulfilled? In particular it is not immediately clear to me that one condition does not exclude the other... $\endgroup$
    – R.P.
    Mar 16, 2017 at 1:17
  • $\begingroup$ Since all the $p_i$ are prime to $n$ you can use the Chinese Remainder Theorem to produce $g$. $\endgroup$
    – Jeff Strom
    Mar 16, 2017 at 1:46
  • $\begingroup$ @JeffStrom I agree that you can find a $g$ such that $(g,p_i)=1$ using Chinese remainder theorem. Can you explain why we can find a $g$ such that $[g]\notin G$ simultaneously. $\endgroup$ Aug 29, 2020 at 6:03
  • $\begingroup$ @S.SundaraNarasimhan,@RP_ . I've filled in the details in the "generalized primes congruent to 3 mod 4" theorem $\endgroup$
    – Jeff Strom
    Aug 30, 2020 at 1:30
  • $\begingroup$ @JeffStrom Thank you for your prompt reply. I will look into it. $\endgroup$ Aug 31, 2020 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.