Proving Infinite Primes

Date: 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/