Why there are infinitely many primes ?
(Euclids Proof)
Prime number is a natural number with exactly two distinct divisor
1 and itself.
Prime :
Is number 12 a prime?
Divisors 0f 12 :
No its not a prime.
Is number 13 a prime ?
Divisors Of 13 :
Yes it is.
Lets understand some basics of prime number :
If a number is not divisible by primes which are lesser than it then we can surely
say its a prime too.
Let me explain,
As exmaple number 23 ,
Which are the numbers are less than 23 and prime as well ??
Here is the list,
Here is 8 numbers which are prime and less than 23.
Now let me conclude,
if all 8 numbers cant divide 23 evenly then 23 its self a prime.
This is applicable for all natural numbers.
Check out,
they cant because 23 is prime.
Insigt 1:
Now let me explain some insight about divisibilty :
What if we make a composite number by multiplying some numbers.
Let me elaborate,
what we can get by multiplying 2 x 3 x 4 x 5 = ?
Its simple.Right ?
whats the insight ?
look number 120 is evenly divided by all those 4 numbers(2,3,4,5).
With reaminder 0 everytime.
That means
their realtion is like this,
* 120 % 2 = 0,
* 120 % 3 = 0,
* 120 % 4 = 0,
* 120 % 5 = 0
We can say it in different ways like 2,3,4,5 is divisors of 120
and
we can say that 2,3,4,5 have one common multiple which is 120.
Lets Dive into the actual proof,
Why there are infinitely many primes ?
There are infinitely many numbers but how large a prime can be thats the
question most often arise.We cant say directly that numbers are infinite so
primes are infinite too.Not logical.
Proofs make it logical.
Insight 2:
Proof :
Lets label all finite primes,
We will now construct the number P to be one more than the product
of all finitely many primes:
The number P has remainder 1 when divided by any prime
pi, i = 1, . . . , n,
making it a prime number as long as P ≠ 1.
Since 2 is a prime number, the list of
pi’s is non-empty. It follows that P
is greater than one and so has two distinct divisors. It is therefore a prime
number.
It can also be seen from the definition of P that it is strictly greater than
any of the pi’s. This contradicts our assumption that there are finitely many
prime numbers. Therefore, there are infinitely many prime numbers.
Alternatively, one can leave out the assumption and let p1, . . . , n be any arbitrary
finite list of prime numbers. Then the conclusion would state that for
any finite list of prime numbers, it is possible to construct a larger prime than
any on the list. This method uses induction.