Proving Infinite PrimesDate: 05/01/2008 at 04:17:33 From: Brendan Subject: Proving infinitude of primes It is easy to show that there are infinitely many primes of form 4n+3. Are there infinitely many primes of form 4n+1? What is an elementary proof (one that does not use Quadratic Reciprocity, since I have not learned it)? My teacher has proven that every prime of form (a^2 + b^2) is of form (4n+1). Thus, a simple way to proceed is to show that there exist infinitely many primes of form (a^2 + b^2). Another way, which I think is more promising is to show that: Lemma. Every odd prime divisor of a^2 + 1 is of form 4n+1. And then we can use lemma to show that if there are finitely many primes of 4n+1 then (p1*p2*...*pn)^2 + 1 is another such prime. However, I cannot prove lemma. Can you prove lemma please? Date: 05/02/2008 at 11:05:52 From: Doctor Jordan Subject: Re: Proving infinitude of primes Hi Brendan, Suppose p_1,...,p_N were all the primes of the form 4n+1. Let M = (2p_1 ... p_N)^2 + 1. M is not divisible by 2 and is not divisible by any of p_1,...,p_N. Since p_1,...,p_N are all the primes of the form 4n+1, all the prime factors of M must therefore be of the form 4n+3. Let p be one of these prime factors. So (2p_1 ... p_N)^2 + 1 = 0 mod p Hence (2p_1 ... p_N)^2 = -1 mod p. This tells us that -1 is a quadratic residue mod p. But -1 is a quadratic residue mod p if and only if p = 1 mod 4, which is a contradiction. Therefore there must be a prime of the form 4n+1 that is bigger than p_N. Therefore there are infinitely many primes of the form 4n+1. If you haven't seen a proof that -1 is a quadratic residue mod p if and only if p = 4n+1, look for a proof in your textbook and if you can't find one write back. - Doctor Jordan, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/