Euclid’s theorem – Proof of Unlimited Prime Numbers

A prime number is defined as a positive integer that can only be divisible by 1 and itself. The proof that there are infinitely many prime numbers is as follows:

Proof: Suppose there are finite prime numbers, let them be p1, p2, p3,…,pn, then their product N=p1p2p3…pn, since N is a positive integer, N+1 is also a positive integer , and N+1 cannot be divisible by p1,p2,p3,…,pn, so N+1 must be a prime number, which contradicts the assumption, so there are infinitely many prime numbers.

The proof that there are an infinite number of prime numbers is known as Euclid’s theorem. Euclid’s theorem states that if you take any finite set of prime numbers, then you can always find a prime number that is not in the set. 

To prove this theorem, we will use the method of contradiction in Math. Suppose that there is a finite set of prime numbers, P = {p1, p2, p3, …, pn}. We will assume that this set contains all the prime numbers. 

Now, let’s consider the number N = p1 * p2 * p3 * … * pn + 1. This number is greater than any of the prime numbers in the set P, since it is the product of all the prime numbers in the set plus one. 

Now, we will show that N is either a prime number or a composite number. If N is a composite number, then it must be divisible by some prime number q, where q is not in the set P. This means that q is a prime number that is not in the set P, which contradicts our assumption that the set P contains all the prime numbers. 

Therefore, N must be a prime number, which means that there is a prime number that is not in the set P. This contradicts our assumption that the set P contains all the prime numbers, and thus proves that there are an infinite number of prime numbers.

–EOF (The Ultimate Computing & Technology Blog) —