Skip to main content

Prime numbers - Do they end at a point?

Prime numbers are one of the most speculated topics in mathematics. Mathematicians have pondered about them enough to arrive at a proper conclusion to the above question.

Let us look at the first few prime numbers:
$$2\quad3\quad5\quad7\quad11\quad13\quad17\quad19\quad23\quad29\quad31\quad37\quad41$$ Let us now look at the first few prime numbers after $100000$:
$$100003\quad100019\quad100043\quad100049\quad100057\quad100069\quad100103\\100109\quad100129\quad100151\quad100153\quad100169\quad100183$$ If you look closely, you may notice that the average separation between consecutive prime numbers between $100003$ and $100183$ is larger than that of $2$ and $41$. Naturally, our brain thinks that this separation increases on and on as we go to larger numbers, and at one point the set of prime numbers terminate. But that is not the case. It is proven that there are infinitely many prime numbers.

The Proof:

Euclid had the same question we have today, and he gave a beautiful proof that is quoted even today for proving that the set of prime numbers do not terminate.

Let us assume that there are only a finite number of primes, name that set $P$.
$$P = \lbrace a_1, a_2, a_3,...,a_n \rbrace$$
Consider a number $A$ such that
$$A = a_1\times a_2\times a_3\times a_4\times ...\times a_n + 1$$
Since the prime number list ended at $a_n$, $A$ must not be a prime number. So $A$ must have a factor that belongs to the set $P$.

Let $a_m$ be the factor of $A$ where $1\le m\le n$. But it is clear that when $A$ is divided by $a_m$, it leaves a remainder 1! But this contradicts the fact that factors leave a remainder of 0 when dividing the number.

Thus, the original assumption that there is a finite list of prime numbers is false. Hence it is proved by the method of contradiction that there are infinitely many prime numbers.
Labels:

Comments

Post a Comment

Popular posts from this blog

Factorials, and the Gamma Function

What is the Gamma function? What does it have to do with the factorial of a number? And why does such a formula even work? The Factorial In our high school combinatorics course, we were introduced to the factorial of a natural number. We defined the factorial of a number $n$ to be the product of all the natural numbers till $n$. Or symbolically: $$n! = 1 . 2 . 3 ... (n-2)  (n-1)  n$$ This is a very useful function in Counting problems. This function also pops up in the exponential function: $$e^x = 1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...$$ Setting this aside, we think: can we 'extend' this function to all real number? Surely, even if we were to come up with such a function, what would it mean to take this new 'factorial' of some real number? Well, let's take a look at one important property of the factorial function: $$n! = n(n-1)!$$ and this is true for all natural numbers $n$. So, even if we came up with this homologous function, we...
Post a Comment
Read more

The $\operatorname{erf}$ function

Can a function be 'defined' as the anti-derivative of another function? $\operatorname{erf}$ is one such function. Even though it has various proper infinite series expansions (as in Wolfram MathWorld - Erf ), it is defined by mathematicians as such: $$\operatorname{erf}(z) \equiv \frac{2}{\sqrt{\pi}}\int_0^ze^{-t^2}dt$$ This function has extensive implications in statistics, and can be used to express the integral of $e^{-x^2}$ and $e^{x^2}$. See the post that tries to find  integral of $e^{x^2}$  - we need not use integration by parts there, but rather can use the $\operatorname{erf}$ function. Source: Wolfram MathWorld
Post a Comment
Read more

Why $y^2 = x^3 + 7$ has no integral solutions?

Consider the given equation... $$y^2-7=x^3=(x^{\frac{3}{2}})^2$$ $$y^2-(x^{\frac{3}{2}})^2=7$$ If $x^{\frac{3}{2}}$ is a decimal, then $y$ should also be some decimal to make the equation an integer, i.e., $7$. So $y$ will be a decimal in this case. But consider when $x^{\frac{3}{2}}$ is an integer. The only integers whose difference of squares is $7$, is $4$ and $3$ (why?). $$4^2 - 3^2 =7$$ But compare it to the equation $y^2-(x^{\frac{3}{2}})^2=7$. Then $$x^{\frac{3}{2}} = 3$$ $$x = 3^{\frac{2}{3}}$$ But here $x$ is a decimal! Therefore, at least one of the variables $x$ and $y$ is a decimal in the given equation, thus proving the fact that it has no integral solutions.
Post a Comment
Read more