Question

Show that there are infinitely many primes.

Answer 1

Hint: We recall the definition of prime number. We assume the negation of the statement and consider finitely many primes ${{p}_{1}}<{{p}_{2}}<{{p}_{3}}...,{{p}_{n}}$ whose product added one we denote as $N={{p}_{1}}{{p}_{2}}...{{p}_{n}}+1$. We prove that $N$ either can be a prime or there is a prime other than ${{p}_{1}}<{{p}_{2}}<{{p}_{3}}...,{{p}_{n}}$ which will contradict our assumption.

Complete step-by-step answer:
We know that prime numbers are natural numbers which are greater than 1 and have two factors: the number 1 and the prime itself. \[\]
We are given the statement “there are infinitely many primes”. We shall prove it by method contradiction. So let us assume the negation “there are not infinitely many primes”, which means there are finitely many primes.\[\]
Let us assume that there are only $n$ primes exist in natural number set which we denote as ${{p}_{1}},{{p}_{2}},...,{{p}_{n}}$ with the condition that they are in order which means${{p}_{1}}<{{p}_{2}}<{{p}_{3}}...,{{p}_{n}}$.\[\]
Let us denote the number $N$ such that number $N$ is more than the product of our primes. So we have;
\[N={{p}_{1}}{{p}_{2}}...{{p}_{n}}+1\]
We use Euclid’s lemma of division and that all the primes ${{p}_{1}},{{p}_{2}},...,{{p}_{n}}$ will leave remainder 1 when they will divide $N$. We know that other 1 and the number itself only primes less than that number can exactly divide the number. So $N$ does not have any primes factors since all the primes ${{p}_{1}},{{p}_{2}},...,{{p}_{n}}$ cannot exactly divide $N$. \[\]
So only factors remaining for $N$ is 1 and $N$ itself which makes $N$ a primes. The other possibility is that there is a prime say $p$ greater than ${{p}_{n}}$ which can exactly divide $N$. We see in both possibilities that there has to be prime either $N$ or $p$ greater than ${{p}_{n}}$ but we assumed the only primes that exist are ${{p}_{1}},{{p}_{2}},...,{{p}_{n}}$ which is contradicted by our conclusion. \[\]
So we reject our assumption that there are finitely many primes and hence it is proved that there are infinitely many primes.\[\]

Note: We note if $a$ is the dividend , $d$ is the divisor, $q$ is the quotient and $r$ is the remainder then according to Euclid’s lemma $a=dq+r$. If $r=0$ then we call $d,q$ as the factors of $a$ and also day $d$ exactly divides $a$. If ${{f}_{1}},{{f}_{2}}$are factors of $a$ then ${{f}_{1}}{{f}_{2}}$are also factors of $a$. The numbers which are not prime except 1 are called composite numbers.