Prime Numbers

Prime Numbers

A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers other than 1 and itself. In other words, a prime number has exactly two distinct positive divisors: 1 and itself.

For example:

• 2 is a prime number because its only divisors are 1 and 2.
• 3 is a prime number because its only divisors are 1 and 3.
• 4 is not a prime number because it can be formed by multiplying 2 and 2 (2 * 2 = 4).

Prime numbers play a fundamental role in number theory and mathematics in general. The set of prime numbers is infinite, and every integer greater than 1 can be uniquely expressed as a product of prime numbers, a concept known as the fundamental theorem of arithmetic.

Historical proofs

The concept of an infinite set of prime numbers has been a fascinating topic in mathematics for centuries.

Ancient Greece: Euclid's Proof (circa 300 BC):

• Euclid, a Greek mathematician, provided one of the earliest and most famous proofs of the infinitude of prime numbers.
• His proof is found in "Elements," specifically in Book IX, Proposition 20. The proof is often referred to as Euclid's proof by contradiction.
• The basic idea is to assume that there is a finite set of prime numbers, and then construct a new number that is not divisible by any of them, leading to a contradiction.
• This contradiction implies that our assumption of a finite set of primes must be false, and therefore, there must be an infinite number of prime numbers.
• In about 200 BC the Greek Eratosthenes devised an algorithm for calculating primes called the Sieve of Eratosthenes.

Ancient India: Work of Bhaskara (circa 1150 CE):

• Indian mathematicians also made significant contributions to the understanding of prime numbers. Bhaskara, an Indian mathematician, discussed prime numbers in his work "Lilavati."
• He explored the divisibility rules for various numbers and provided methods for finding prime numbers.

18th Century: Euler's Formula (circa 1737):

• Euler, a Swiss mathematician, made notable contributions to number theory. In 1737, he provided an elegant proof of the infinitude of primes using a series.
• Euler's proof involves considering the harmonic series (1 + 1/2 + 1/3 + 1/4 + ...). He showed that if you multiply all these fractions and add 1, the result is not divisible by any prime, indicating that there must be infinitely many primes.

20th Century: More Rigorous Proofs:

• In the 20th century, more rigorous proofs of the infinitude of prime numbers emerged, often involving more advanced mathematical concepts.
• Notable contributions include Paul Erdős and Atle Selberg's work on the "elementary proof" of the infinitude of primes (1949) and Alain Connes' adaptation of ideas from non commutative geometry to prove a generalised form of the infinitude of primes (1976).

Let's take a closer look at the Sieve of Eratosthenes:

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit. It is a straightforward and efficient method that eliminates multiples of each prime, gradually "sieving" out the non-prime numbers. The algorithm is named after the Greek mathematician Eratosthenes, who described it in his work "Introduction to Arithmetic" around 240 BC.

Here's a step-by-step explanation of how the Sieve of Eratosthenes works:

• Create a List of Numbers: Start with a list of integers from 2 to the desired upper limit. These are the numbers you want to check for primality.
• Select the First Prime (2): Begin with the first number in the list (2), which is a prime number.
• Cross Out Multiples: Cross out all multiples of the selected prime number in the list, except for the prime number itself. For example, if you started with 2, cross out all multiples of 2 in the list (4, 6, 8, 10, ...).
• Select the Next Uncrossed Number: Move to the next uncrossed number in the list. This will be the next prime number.
• Repeat Steps 3-4: Repeat the process of crossing out multiples and selecting the next uncrossed number until you have processed all numbers in the list.
• Result: The remaining uncrossed numbers in the list are all prime.

Let's find the prime numbers up to 30 using the Sieve of Eratosthenes:

• Start with the list: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30.
• Select 2 as the first prime and cross out its multiples: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.
• Move to the next uncrossed number, which is 3, and cross out its multiples: 9, 15, 21, 27.
• Move to the next uncrossed number, which is 5, and cross out its multiples: 25.
• Move to the next uncrossed number, which is 7, and cross out its multiples: there are none remaining in the range up to 30.
• Continue this process until all numbers have been either crossed out or marked as prime.

After completing these steps, the remaining numbers (2, 3, 5, 7, 11, 13, 17, 19, 23, 29) are the correct prime numbers up to 30.

The Sieve of Eratosthenes is a simple and efficient algorithm, especially for finding small primes. It has been widely used throughout history and remains a fundamental method in number theory and computer science.

R code for Data Visualisation

A Markdown document with a Prime Number generator for a print, plot and csv file save (output below): - link. (Does not generate the first prime: 2).

The infinitude of prime numbers is now a well-established result in mathematics. While the historical proofs varied in sophistication, they all shared the core idea of assuming a finite set of primes, leading to a contradiction, and thereby establishing the existence of an infinite set of prime numbers.

link To my project about Infinity on Kaggle.

Conclusion
Prime numbers are fundamental to number theory and have fascinated mathematicians for centuries. Their infinite nature has been established through various proofs, each contributing to a deeper understanding of these essential building blocks of mathematics. The Sieve of Eratosthenes, an ancient algorithm, remains a practical method for finding prime numbers, while modern computer programs and techniques continue to explore the vast realm of primes. The study of prime numbers continues to yield new insights and connections, making them a rich and enduring area of mathematical exploration.

Patrick Ford 𓐍