Infinitude of Primes, and Related Questions

প্রাইমের সংখ্যা অসীম : ইউক্লিডের প্রমাণ

প্রাইম সংখ্যা হল একের থেকে বড় এমন একটা সংখ্যা যাকে এক আর ওই সংখ্যা ছাড়া অন্য কোনো সংখ্যা দিয়ে ভাগ করা যায় না। প্রথম দিকের কয়েকটা প্রাইম সংখ্যার উদাহরণ হল: $2, 3, 5, 7, 11, \cdots$। তোমরা যদি ভালমত খেয়াল কর, তাহলে দেখবে যে প্রাইম সংখ্যা প্রথম দিকে অনেক ঘন ঘন পাওয়া যায়; পরের দিকে প্রাইমের সংখ্যা কমতে থাকে। তাই স্বাভাবিকভাবেই তোমাদের মনে প্রশ্ন আসতে পারে: এরকম কি কখনও হবে যে প্রাইমের সংখ্যা কমতে কমতে একসময় শেষ হয়ে যাবে? আমরা এই আর্টিকেলে এই প্রশ্নটার উত্তর দেওয়ার চেষ্টা করব।

এই প্রশ্নের উত্তর সবার প্রথমে দিয়েছিল ইউক্লিড। সে প্রমাণ করে দেখিয়েছিল যে এরকম কখনো হবে না। মানে প্রাইমের সংখ্যা আসলে অসীম।

সাধারণত ইউক্লিডের প্রমাণটা একটা প্রুফ বাই কন্ট্রাডিকশন হিসেবে পেশ করা হয়। কিন্তু ইউক্লিডের অরিজিনাল প্রমাণটা কিন্তু একটা ডাইরেক্ট প্রমাণ।

ইউক্লিডের প্রমাণ শুরু করার আগে আমাদের একটা জিনিস প্রথমে জানতে হবে। আর সেটা হচ্ছে একের চেয়ে বড় যেকোনো পূর্ণসংখ্যার কমপক্ষে একটা প্রাইম গুণনীয়ক আছে।

আমরা শুরু করব একটা প্রাইমের সসীম সেট দিয়ে। এমন একটা সেটের কথা চিন্তা কর যার মধ্যে $n$-সংখ্যক প্রাইম আছে: $p_1, p_2, p_3, \cdots p_n$। সে প্রাইমগুলো যেকোনো কিছু হতে পারে। শুধু প্রাইম হলেই চলবে।

এবার নতুন একটা নাম্বার $P$ বানাও যেটা হল ওই সেটের সবগুলো সংখ্যার গুণফলের চেয়ে এক বেশি। মানে $P= p_1 p_2 p_3 \cdots p_n+1$।

তোমরা যদি উপরের প্রশ্নটার উত্তর ঠিকমত দিতে পার, তাহলে তোমরা হয়তো বুঝতে পারছ এখন কী হতে চলেছে। $P$ এর একটা প্রাইম ফ্যাক্টর আছে (এক ছাড়া সবারই থাকে)। কিন্তু ওই প্রাইম ফ্যাক্টরটা আমাদের সেটে নেই। কারণ আমাদের সেটের যেকোনো সংখ্যা দিয়েই $P$-কে ভাগ করলে ভাগশেষ এক হয়। সুতরাং প্রাইমের যেকোনো সসীম সেটের জন্যই একটা নতুন প্রাইম ($P$ এর প্রাইম ফ্যাক্টর) জেনারেট করা সম্ভব যেটা ওই সেটে নেই। এর মানে কোনো সসীম সেটই সকল প্রাইমকে ধারণ করতে পারে না। অর্থাৎ, প্রাইমের সংখ্যা অসীম।

Infinitude of Primes: Famous Proof of Euclid

There are many proofs of there being infinitely many primes. The most famous one is Euclid's proof, which uses the technique of proof by contradiction. It goes as follows.

Suppose that there are only finitely many primes, and they are $p_1, p_2, \ldots, p_n$. These $n$ primes are arranged in increasing order.

Now consider the number $N = p_1p_2\cdots p_n + 1$. By our assumption, $N$ is not a prime. There must be a prime number $p$ so that $p \mid N$. Since for all $1 \le i \le n$, obviously $p_i \mid p_1p_2 \cdots p_n$, but $p_i \nmid 1$, so $p_i \nmid N$. In other words, none of the primes in our assumed finite set divide $N$. Therefore, there must exist another prime $p_{n+1}$ not in our original set such that $p_{n+1} \mid N$, contradicting our original assumption that there were finitely many primes. In conclusion, there are infinitely many primes.

This is a common misconception. While there are instances when $N$ is prime (for example, suppose we had $p_1 = 2$ and $p_2 = 3$; then $N = 7$, which is indeed prime), this is not always the case. Suppose our set of primes consisted of $p_1 = 2$ and $p_2 = 3$ and $p_3 = 5$ and $p_4 = 7$ and $p_5 = 11$ and $p_6 = 13$. Then $N = 30031$, which is $59 \times 509$. However, our proof guarantees the existence of another prime because $2 \nmid 30031$ and $3 \nmid 30031$ and $5 \nmid 30031$ and $7 \nmid 30031$ and $11 \nmid 30031$ and $13 \nmid 30031$. It must be emphasized that the algorithm $N = p_1p_2\cdots p_n + 1$ does generate infinitely many primes, but it does not generate all the primes.

This proof by Euclid was one of the earliest and simplest ways to show the infinitude of primes. However, there are numerous other ways. Kummer's proof was nearly same. He used $n!+1$ insted of $p_1\cdots p_n+1$. Some noteworthy ones include the use of Fermat numbers, as well as Furstenberg's topological proof. We will discuss them later, for example, check out the proof by Goldbach.

Infinitude of Primes: Goldbach's Proof

You're probably aware by now that there are infinitely many primes. You've also probably heard of Euclid's proof of infinitude of primes. In short, Euclid's proof basically tells you that given a finite set of prime numbers, it is possible to generate another prime number that is not in that set. So a finite set can not contain all the prime numbers.

In this article, we'll see another proof that there are infinitely many prime numbers. But before that, we need to know what it means for two numbers to be coprime to each other. This proof is due to Goldbach, which was written to Euler in $1730$.

Now that we have that cleared up, let's get down to business.

We're going to use something called Fermat numbers in this proof. Fermat numbers are numbers of the form $2^{2^n}+1$ where $n$ is a non-negative integer. Fermat numbers are named after the French mathematician Pierre de Fermat.

Fermat conjectured that all Fermat numbers are prime, that is all the numbers of the form $2^{2^n}+1$ were prime numbers. Later on, Euler proved him wrong. Notice that if Fermat's conjecture were true, we'd immediately be able to conclude that there are infinitely many prime numbers. However, Fermat's conjecture is not true since $2^{2^5}+1=2^{32}+1=4294967297=641 \times 6700417$, which is definitely not a prime.

The motivation behind the proof we're going to see is the following fact: if we have a list of infinitely many integers that are all coprime to one another, then there are infinitely many primes. Because each time you add a number co-prime to every other number, if the number is greater than $1$, it will have a prime factor, which is different from the prime factors of all other members.

If this doesn't make sense right now, don't worry. We'll come back to this later.

Let $F_n=2^{2^n}+1$. What happens when you take the product of several consecutive $F_i$'s starting from $F_0$? I encourage you to play with this for a while. Only after you think you've found a pattern should you hit 'Continue'.

Did you find $\displaystyle\prod_{i=0}^{n-1} F_i=F_{n}-2$? A good exercise would be proving this using induction.

What this essentially says is that if some positive integer $k$ divides both $F_i$ and $F_n$ (with $i<n$), then $k$ is either $1$ or $2$. However $k$ can not be equal to $2$ since all the $F_i$ are odd.

In other words, all Fermat numbers are co-prime to one another.

This means that every Fermat number has a prime factor that does not divide any of the other Fermat numbers. Since there are infinitely many Fermat numbers, this means there are infinitely many primes.

We're done!

Infinitude of Primes: Saidak's Proof

We've already seen a couple of proofs of the infinitude of prime numbers. In this article we'll go through another one. What makes this proof special is its sheer simplicity. This proof is due to Filip Saidak.

If you've read this post, then you know that one way to prove the infinitude of primes is to somehow generate infinitely many numbers that are all coprime to one another. We used Fermat numbers in that proof.

But to find infinitely many such numbers, one doesn't have to look that far.

Two consecutive positive integers are always coprime to each other. In other words, if $n$ is a positive integer, then $n$ and $n+1$ are coprime.

Now consider the number $N_2=n(n+1)$. If $n>1$, $N_2$ has at least two prime factors.

Why? Remember that $n$ and $n+1$ are coprime. So $n$ has a prime factor that does not divide $n+1$. Similarly, $n+1$ has a prime factor that does not divide $n$. That means their product, $N_2$ has to have at least two distinct prime factors.

Now consider the numbers $N_2$ and $N_2+1$. They are coprime to each other. So, their product, $N_3=N_2(N_2+1)$ has to have at least three distinct prime factors.

Do you see where we're going with this? We can keep doing this indefinitely and generate a number that has as many distinct prime factors as we want it to have. The conclusion: there are infinitely many primes.

This is the sort of proof that makes you go, "Why didn't I think of that?" The surprising thing is no one did think of it until recently. This is a relatively "recent" proof and was published in 2005.

So simple, yet no one thought of it for that many years!

Infinitude of Primes: A Combinatorial Proof by Perott

The proof is due to Perott, which dates back to almost $1801-1900$.

Up to $100$, how many numbers are divisibe by $3$? Note that, the answer is $33$ because $33\cdot3=99$ and $34\cdot3=102>3$. Using Floor function, we can say that this is $\left\lfloor\frac{100}3\right\rfloor$.

A natural number is called square-free if it is not divisible by any square greater than $1$. So, $3$ and $30$ are square-free whereas $4$ is not. We can state this another way. A number is square-free if and only if it is divisible by $p^2$ for a prime $p$.

If you clicked $53$, think again and see that the answer is

$$\left\lfloor\dfrac{100}3\right\rfloor+\left\lfloor\dfrac {100}5\right\rfloor-\left\lfloor\dfrac{100}{15}\right\rfloor$$

We can see that this is less than $\left\lfloor\dfrac{100}3\right\rfloor+\left\lfloor\dfrac {100}5\right\rfloor$.

Next, Number of divisors post says that the number $p_1\cdots p_k$ has $\underbrace{(1+1)\cdots(1+1)}_{k\text{ times}}=2^k$ divisors.

We will also need the following fact:

$$\sum_{i\geq1}\dfrac1{i^2}<2$$

In fact, Euler showed that:

$$\sum_{i\geq1}\dfrac1{i^2}=\dfrac{\pi^2}6$$

But this is not necessary for now. Here is a proof of what we need. We will use the fact that if $a>b$ then $\frac1a<\frac1b$, specially, $\frac1{n+1}<\frac1n$ for $n\geq1$.

\begin{eqnarray*} \sum_{i\geq1}\dfrac1{i^2}

& < & 1+\sum_{i\geq2}\dfrac1{i(i-1)}\newline & = & 1+\sum_{i\geq2}\left(\dfrac1{i-1}-\dfrac1{i}\right)\newline & = & 1+1=2\newline \sum_{i\geq1}\dfrac1{i^2} & = & 2-m\text{ for some }m>0 \end{eqnarray*}

Let's get to the proof already! Like before, we assume there are only $k$ primes $p_1,\ldots,p_k$. Take $n=p_1\cdots p_k$ and any integer $N>n$. Since there are no primes besides these $k$, any square-free number must be a divisor of $n$. Therefore, there are $2^k$ square-free numbers. Now, the number of numbers upto $N$ which is divisible by $p$ is $\left\lfloor\dfrac N{p^2}\right\rfloor$. So, we can surely say the number of numbers not divisible by any of $p_1^2,\ldots,p_k^2$ is less than

\begin{eqnarray*} \left\lfloor\dfrac N{p_1^2}\right\rfloor+\ldots+\left\lfloor\dfrac N{p_k^2}\right\rfloor & = & \sum_{i=1}^k \left\lfloor\dfrac N{p_i^2}\right\rfloor \end{eqnarray*} Since any number is either square-free or not square-free, we have \begin{eqnarray*} N &\leq&2^k+\sum_{i=1}^k \left\lfloor\dfrac N{p_i^2}\right\rfloor \newline & < & 2^k+\sum_{i=1}^k \dfrac N{p_i^2}\newline & < & 2^k+n\sum_{i=1}^k\dfrac 1{p_i^2}\newline & < & 2^k+N\left(\sum_{i\geq}\dfrac 1{i^2}-1\right)\newline & < & 2^k+N(1-m)\newline Nm & < & 2^k \end{eqnarray*} Note that, $2^k$ is fixed, whereas we can make $Nm$ as large as we can since $N>n$ any integer. So, for those $N$, we get a contradiction. $W^5$ (which was what we wanted)!

Infinitude of Primes: Euler's Proof

We have already seen the ways Euclid, Kummer and Goldbach used to prove that there are infinitely many primes. It would be odd to leave out Euler (one of my most favorite mathematicians).

Euler investigated the sum (which is known as Harmonic Series):

$$S=\dfrac11+\dfrac12+\ldots+\dfrac1n+\ldots\infty$$

Consider the sum in terms of prime factorization.

Obviously, $1,\dfrac12,\dfrac1{2^2},\ldots$ are part of the series. So are $\dfrac13,\dfrac1{3^2},\ldots$ and $\dfrac15,\dfrac1{5^2}$ and so

on. If you understood the fact we showed above, note that $\dfrac12\cdot\dfrac13$ gives $\dfrac16$. Similarly, $\dfrac1{2^2}\cdot\dfrac13=\dfrac1{12}$ and $\dfrac13\cdot\dfrac15=\dfrac1{15}$ and so on.

We know that, any number can be written as a product of primes in a unique way. Therefore, when we are multiplying some powers of primes, we will get a unique number. In other words, the same number won't appear twice. Now, notice the following sum:

\begin{eqnarray*} & & \left(1+\dfrac12+\dfrac1{2^2}+\ldots\right)\cdot\left(1+\dfrac13+\dfrac1{3^2}+\ldots\right)\newline & = & 1+\dfrac12+\dfrac1{2^2}+\dfrac13+\dfrac1{2\cdot3}+\dfrac1{2^2\cdot3}+\dfrac1{3^2}+\dfrac1{2\cdot3^2}+\dfrac1{2^2\cdot3^2}+\ldots\newline & = & 1+\dfrac12+\dfrac14+\dfrac13+\dfrac16+\dfrac1{12}+\dfrac19+\dfrac1{18}+\dfrac1{36}+\ldots \end{eqnarray*} Unique prime factorization guranatees that none of $2,4,6$ or $18$ will appear anywhere in the series again. That is, any number of the form $2^i3^j$ will appear exactly in this series. Similarly, if we considered all the numbers generated by $2^i3^j5^k$, we would have numbers like $30, 60$ or $90$ exactly once in the series. So, going this way, we can see that the sum $S$ is nothing but the product of $1+\dfrac1p+\dfrac1{p^2}+\ldots$ for all prime $p$.

\begin{eqnarray*} S & = & 1+\dfrac12+\dfrac13+\dfrac14+\ldots\newline & = & \left(1+\dfrac12+\dfrac1{2^2}+\ldots\right)\cdot\left(1+\dfrac13+\dfrac1{3^2}+\ldots\right)\cdot\left(1+\dfrac15+\dfrac1{5^2}+\ldots\right)\newline & = & \prod_{p\in\mathbb P}1+\dfrac1p+\dfrac1{p^2}+\ldots \end{eqnarray*} where $\mathbb P$ is the set of primes. The infinite geometric series $1+r+r^2+\ldots$ where the ratio $r$ is such that $|r|<1$, has a finite sum $\dfrac1{1-r}$. Here, $r=\dfrac1p<1$ of-course. Therefore, we can say that

$$1+\dfrac1p+\dfrac1{p^2}+\ldots=\dfrac1{1-\frac1p}=\dfrac p{p-1}$$

This means that,

$$S = 1+\dfrac12+\dfrac13+\ldots=\prod_{p\in\mathbb P}\dfrac p{p-1}$$

Our intuition says that, $S$ is infinite, though we can't gurantee that without proving it first. In the post Harmonic series diverges it is already proved that $S$ is infinite. A series diverges if it has an infinite sum. If the number of primes is finite, then the product of $\dfrac p{p-1}$ would be finite too. But it gives us a contradiction. Thus, the number of primes must be infinite.

This proof should tell you how great Euler's insight was! May be you will understand why Euler is one of the most favorite mathematicians of the author.

Infinitude of Primes: A Proof by Schorn

Yet another proof of infinitude of primes. I wanted to write it because it is as elegant as the other ones we saw earlier. We will use Euclidean Algorithm to find greatest common divisor.

Schorn's idea was basically a revision of Goldbach's idea, which is described in this post. First we will prove the following: $$\gcd(j(n!)+1,i(n!)+1)=1$$ for $1\leq i<j<n+1$. We can write $j=i+k$, so $1\leq k<n$. Thus,

\begin{eqnarray*} \gcd(n!(i+k)+1,i(n!)+1) & = & \gcd(i(n!)+1+n!k,i(n!)+1)\newline & = & \gcd(n!k,i(n!)+1) \end{eqnarray*} from Euclidean algorithm after subtraction. We also know that if $\gcd(a,b)=1$ then $\gcd(a,bc)=\gcd(a,c)$. Clearly $\gcd(n!,i(n!)+1)=1$ since $i(n!)+1$ leaves a remainder of $1$ when divided by $n!$. Therefore, \begin{eqnarray*} \gcd(n!(i+k)+1,i(n!)+1) & = & \gcd(n!k,i(n!)+1)\newline & = & \gcd(k,i(n!)+1) \end{eqnarray*} Since $k<n$, we also have that $k$ divides $n!$, so $i(n!)+1$ leaves a remainder of $1$ when divided by $k$ too. Finally, we have \begin{eqnarray*} \gcd(n!(i+k)+1,i(n!)+1) & = & \gcd(k,i(n!)+1) = 1 \end{eqnarray*} From this we can say, the integers $n!i+1$ for $1\leq i\leq n$ are co-prime. And so, we are done.

Infinitude of Primes: Yet Another Proof

We hope, you aren't getting bored of so many proofs of the same theorem. Here is another one I couldn't help sharing. This elegant proof is due to J. Braun ($1896$).

Take the primes $p_1,\ldots,p_k$, $P=p_1\cdots p_k$ and set

$$\dfrac1{p_1}+\ldots+\dfrac1{p_k}=\dfrac a{P}$$

Note that, $$\dfrac aP>\dfrac12+\dfrac13+\dfrac15=\dfrac{31}{30}>1$$ So $a>P$, and thus, $a$ has a prime divisor $p$. So $p$ must divide $P$, if it is not a new prime.

$$a=\dfrac P{p_1}+\ldots+\dfrac Pp+\ldots+\dfrac P{p_k}$$

Obviously, $p$ divides $\frac Pq$ if $p\neq q$. Therefore, we have $p$ divides $\dfrac Pp$, since $p$ divides $a$ and $\frac Pq$ for all other primes $q$. But then the equation gives that $p$ divides $\frac Pp$, a contradiction! $W^5$.