Special cases of Dirichlet's theorem - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T21:04:34Z http://mathoverflow.net/feeds/question/32624 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32624/special-cases-of-dirichlets-theorem Special cases of Dirichlet's theorem falagar 2010-07-20T12:14:10Z 2010-07-23T22:05:42Z <p>Dirichlet's theorem states that for any coprime $k$ and $m$ there exists infinitely many primes $p$ such that $p \equiv k \pmod m$.</p> <p>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$.</p> <p>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$.</p> <p>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_k + 3$.</p> <p>Those constructions could also be applied to some other special cases as well.</p> <p>Are there any other special cases for which there exists a simple non-analytic proof which don't use any of those two constructions?</p> http://mathoverflow.net/questions/32624/special-cases-of-dirichlets-theorem/32635#32635 Answer by Daniel Litt for Special cases of Dirichlet's theorem Daniel Litt 2010-07-20T13:31:37Z 2010-07-21T13:17:51Z <p>There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in <a href="http://stanford.edu/~dalitt/primes1mod4.pdf" rel="nofollow">this note</a>. 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.</p> <p>Edit: <a href="http://projecteuclid.org/DPubS?verb=Display&amp;version=1.0&amp;service=UI&amp;handle=euclid.facm/1229442627&amp;page=record" rel="nofollow">This paper</a> 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.</p> <p>Here is an open-access <a href="http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/dirichleteuclid.pdf" rel="nofollow">paper</a> by Keith Conrad expositing this impossibility theorem and giving some background.</p> <p>Edit 2: Here is the <a href="http://www.jstor.org/pss/2310975" rel="nofollow">paper</a> 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.</p> http://mathoverflow.net/questions/32624/special-cases-of-dirichlets-theorem/32663#32663 Answer by Robin Chapman for Special cases of Dirichlet's theorem Robin Chapman 2010-07-20T17:40:39Z 2010-07-20T17:40:39Z <p>As Daniel has pointed out, there is an elementary proof that for each $n$ there are infinitely many primes $p$ with $p\equiv1$ (mod $n$). There is an also an elementary proof that for each $n$ there are infinitely many primes $p$ with $p\equiv-1$ (mod $n$). This can be found in Nagell's <em>Introduction to Number Theory</em> section 50 in the second edition.</p>