Infinitely many primes via Fermat Numbers

Standard proof of infinitude of prime numbers (due to Euclid) goes as follows:

Assume, to the contrary, that there were only finitely many primes, say p_1, p_2, ..., p_k are all of them. Then, consider the number N=p_1p_2\cdots p_k+1. We ask whether N is prime or not. Well, since N is strictly bigger than all of the numbers p_1,p_2,...,p_k, by assumption N cannot be prime (because all the primes are assumed to be p_1,p_2,...,p_k). So N must be composite. But then a prime factor of N must be p_j for some j with 1\le j\le k. Now observe that p_j divides both N and p_1p_2\cdots p_k, and so divides the difference N-p_1p_2\cdots p_k=1. We have shown that p_j divides 1, and this is clearly a contradiction (because every prime is strictly larger than 1).

Let’s show another proof of infinitude of prime numbers using Fermat Numbers. For each n\in\mathbb{N} we define F_n=2^{2^{n}}+1. We call F_n the n-th Fermat number. The idea is to show any two Fermat numbers are pairwise relatively prime. Why would this show infinitude of primes? Because if two numbers are pairwise relatively prime, they have distinct prime factors. And since there are infinitely many Fermat numbers, if every pair of them were relatively prime, then clearly we would generate infinitely many primes.

So it remains to show that \gcd (F_n, F_m)=1 for every m,n\in\mathbb{N} with m>n. Let d=\gcd (F_m, F_n). Observe that

\displaystyle F_m - 2 = 2^{2^{m}}-1=(2^{2^{n+1}})^{2^{m-n-1}}-1

Using the factorization x^q-1=(x-1)(x^{q-1}+x^{q-2}+\cdots +x+1), we know x-1 divides x^q-1. So the above equation implies that 2^{2^{n+1}}-1 divides F_m-2. On the other hand, we have

\displaystyle 2^{2^{n+1}}-1=(2^{2^{n}}-1)(2^{2^{n}}+1)=(2^{2^{n}}-1)F_n

Thus, F_n divides 2^{2^{n+1}}-1. But 2^{2^{n+1}}-1 divides F_m-2. Thus, F_n divides F_m-2. By definition of \gcd, we know d divides F_n, and F_m. Since F_n divides F_m-2, it follows that d also divides F_m-2. But then d divides the difference F_m-(F_m-2)=2. We have shown that d divides 2. Since Fermat numbers are odd, their greatest common divisor must also be odd, hence d is odd. We conclude that d=1. This precisely shows that \gcd(F_n,F_m)=1, as desired.

Advertisements
This entry was posted in Uncategorized and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s