Bertrand's Postulate

Bertrand's Postulate says that for any integer n > 1 there is a prime number p such that n < p < 2n. Here's a link to a beautiful and elementary proof of this fact: http://mathforum.org/library/drmath/view/51527.html.

A beautiful solution

Suppose you want to prove that the sum of 1/(m^2 + n^2) diverges as m,n ranges over all positive integers. What do you do?

Here's a very beautiful solution, from one of my students in an undergraduate complex analysis class:

Every prime of the form 4k+1 is expressible as the sum of two squares. Hence the previous sum is bounded below by the sum of 1/p, where p ranges over all primes that are congruent to 1 mod 4. The latter sum diverges. Q.E.D.

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. >.<""