A Nice Proof of "Infinite Primes of Form 4k+1"

Recently, I am writing a set of notes about prime numbers. Certainly I have included the most well-known fact about prime numbers in the set of notes --- there are infinitely many prime numbers. There are various proofs, including the most famous proof from Euclid.

I try to add something more into the set of notes. All prime numbers, except 2, have to be in the form of 4k+1 or 4k+3 (because all the other primes are odd). Two natural follow-up questions are, "Is there infinite number of primes of the form 4k+3?" and "Is there infinite number of primes of the form 4k+1?" The proof can be included in the set of notes as an appendix for more gifted students.

It turns out that the first question is easy to answer, by mimicking the technique from Euclid. If you have never heard this before, try to understand the proof by Euclid from the link above, and adopt the main idea to the "4k+3" question.

The second question, however, is more difficult. I am not sure if there is any simpler elementary solution, but I found a rather fascinating proof on web, using the Fermat's Little Theorem. Let me restate the proof here.

Given any integer N, consider , and p be the smallest prime factor of M.

Since 1, 2, ... , N all do not divide M, p is larger than N. Since p divides , we have



Taking -th power on both sides, we have

....(1)

On the other hand, by Fermat's Little Theorem, for a = 1, 2, ... , N, we have



Multiplying the above formula with a = 1, 2, ... , N, we get

....(2)

Comparing (1) and (2), we get



which implies is even and hence p is of the form 4k+1. As N is chosen arbitrarily, we reach the conclusion: there are infinitely many primes of the form 4k+1.

Is that too difficult for F.3 and F.4 students? I am not sure, but as it is put in the appendix, it is not demanding even I put the proof of Fermat's Last Theorem there. >.<""