Euclid's theorem - Proof of Unlimited Prime Numbers
Tags: math, prime, blog, softwareengineering
Published: 2023-02-08 11:00:14

https://www.youtube.com/y0rpCeA9rcI

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 <a href="https://helloacm.com/teaching-kids-programmaing-generate-prime-numbers-using-sieve-of-eratosthenes-algorithms/" title="Teaching Kids Programming – Generate Prime Numbers using Sieve of Eratosthenes Algorithms">prime numbers</a>, 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 <a href="https://helloacm.com/find-the-10001st-prime-number/" title="Find the 10001st Prime Number">prime number</a> that is not in the set. 

To prove this theorem, we will use the method of contradiction in <a href="https://helloacm.com/how-tall-is-the-table-simple-math-equations/" title="How Tall is the Table? (Simple Math Equations)">Math</a>. Suppose that there is a finite set of prime numbers, P = {p1, p2, p3, ..., pn}. We will assume that this set contains all the <a href="https://helloacm.com/finding-primes/" title="Finding Primes">prime numbers</a>. 

Now, let's consider the number N = p1 * p2 * p3 * ... * pn + 1. This number is greater than any of the <a href="https://helloacm.com/how-to-count-the-prime-number-of-set-bits-in-binary-representation/" title="How to Count the Prime Number of Set Bits in Binary Representation?">prime numbers</a> 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 <a href="https://helloacm.com/what-is-the-largest-prime-factor-of-the-number-600851475143/" title="What is the largest prime factor of the number 600851475143 ?">prime number</a> 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 <a href="https://helloacm.com/teaching-kids-programmaing-generate-prime-numbers-using-sieve-of-eratosthenes-algorithms/" title="Teaching Kids Programming – Generate Prime Numbers using Sieve of Eratosthenes Algorithms">prime number</a> 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 (<a title='The Ultimate Computing & Technology Blog' href='https://helloacm.com'>The Ultimate Computing & Technology Blog</a>) -- 

[Blog Post](https://helloacm.com/euclids-theorem-proof-of-unlimited-prime-numbers/)