Prime Numbers

#folder

Prime, Composite

Definition

A natural number is called a prime if its only positive divisors are 1 and itself. Otherwise, is composite.

Coprime

Definition

Two integers and are coprime if

Prime Factorization (PF)

Proposition

Every natural number can be written as a product of primes

That is, for all natural numbers , there exists prime numbers and , such that

Remark

Actually, the existence of these factors is unique when disregarding order, as stated in the unique factorization theorem

Proof

We prove this by strong induction on , where is the open sentence:

The natural number can be written as a product of primes

Base Case: The statement is true, since is a prime

Inductive Step: Let be an arbitrary integers where

Assume the inductive hypothesis, $P(2) \land .
That is, we assume that the natural number can be written as a product of primes, for all integers

We wish to prove , which says that the natural number can be written as a product of primes.
The integers is either prime or composite.

Case 1: If is a prime, then is immediately true.

Case 2: If is a composite, then we can write , where and are natural numbers such that and .
Therefore, by the inductive hypothesis, and can be written as a product of primes, and hence can be written as a product of primes, proving in this case also.

The result is true for , and hence holds true for all by POSI.

Euclid's Theorem (ET)

Theorem

The number of primes is infinite

Proof

Assume, for the sake of contradiction, that the number of primes is finite, say .
Let primes be denoted by , and consider the integer

Since for all , then cannot equal any of the 's, and hence is not a prime.
Now, , where , for each of the primes .

From the division algorithm, this means that we have remainder when dividing by .
But it is implied that cannot be written as a product of primes, because and since , and hence doesn't divide for all .

This is a contradiction, since by the proposition of Prime Factorization, can be written as a product of primes.

As a result, the statement is true.