Infinitude of primes

From Automated Assistance for Formal Reasoning

Jump to: navigation, search

We want to show that there are infinitely many primes. We will argue this by assuming the opposite and deriving a contradiction.

[edit] Argument

We introduce a finite set P of all primes, and its product m.


Introduce P,m.

Assume for all n \in \mathbb{N}, if n is prime then n \in P.

Assume P is a finite set, P is non-empty, and P \subset \mathbb{N}.

Assume m = P_0 \cdot \ldots \cdot P_{|P|-1}.


The above notation for the product of a subset of \mathbb{R} has equivalent alternatives.


Assert  m = \prod P.

Assert m = \prod_{x \in P} x.


We now demonstrate that the above assumptions allow us to derive a contradiction.


Assert m \in \mathbb{N}.

Assert for any p \in \mathbb{N},

if p is a prime factor of m+1 then
p is not a factor of m,
p is prime,
p \in P,
p is a factor of m,
there is a contradiction.
Personal tools
course projects
ongoing projects