Product Design, Manufacturing & Innovation Resources
Home » Infinite Primes (Euclid’s Proof)

Infinite Primes (Euclid’s Proof)

-300
  • Euclid of Alexandria
Euclid of Alexandria proving infinite primes in a classical study setting.

(generated image for illustration only)

Euclid’s theorem states there are infinitely many prime numbers. The classic proof is by contradiction. It assumes a finite list of all primes \(p_1, p_2, \dots, p_n\). It then considers the number \(P = p_1 p_2 \cdots p_n + 1\). This number \(P\) is either prime or not. If it’s prime, it’s a new prime not on the list.

The proof continues: if \(P\) is not prime, it must be divisible by some prime, say \(q\). This prime \(q\) must be on our assumed complete list of primes. However, if we divide \(P\) by any of the primes \(p_i\) from our list, the remainder is always 1. Therefore, none of the primes on our list can be the factor \(q\). This means \(q\) must be a prime number that was not on our original list. In either case—whether \(P\) is prime or composite—there exists at least one more prime than is contained in any finite list. This contradicts the initial assumption that the set of all primes is finite. Therefore, the set of prime numbers must be infinite. This elegant argument is considered a masterpiece of mathematical reasoning and is often one of the first examples of proof by contradiction taught to students. It appears in Book IX, Proposition 20 of Euclid’s *Elements*.

UNESCO Nomenclature: 1101
– Pure mathematics

Type

Abstract System

Disruption

Foundational

Usage

Widespread Use

Precursors

  • concept of prime and composite numbers (developed by earlier Greek mathematicians like the Pythagoreans)
  • the fundamental theorem of arithmetic (implicitly used, stating every integer greater than 1 is either a prime or a product of primes)
  • the division algorithm
  • logic and the method of proof by contradiction (reductio ad absurdum)

Applications

  • foundation of number theory
  • cryptography (e.g., RSA algorithm relies on the difficulty of factoring large numbers, which is related to the distribution of primes)
  • development of modern algebra and analysis
  • computer science algorithms for primality testing and factorization

Patents:

NA

Potential Innovations Ideas

Due to scrapping bot traffic, currently more than 40k per day, this content is reserved to community members.
> Login < or > Register < (100% free) to access this, so as all other restricted content and tools.

Related to: Euclid’s theorem, prime numbers, infinite primes, proof by contradiction, number theory, Euclid’s elements, primorial, mathematics, ancient Greece, fundamental theorem of arithmetic.

Historical Context

Infinite Primes (Euclid’s Proof)

-300
-550
1750
1790
1800
1844
1874
-300
-450
1585
1779
1799
1801
1850
1875

(if date is unknown or not relevant, e.g. "fluid mechanics", a rounded estimation of its notable emergence is provided)

Related Invention, Innovation & Technical Principles

Full size images and downloads are only available, 100% free, for registered members.

> Login <