1. There are infinitely many prime numbers.

In this post I will be going through the definitions, proposition and methods of proof required to arrive at the result in the title. I want this to be a motivating example for the study of number theory, before I delve deeper into the topic in future posts. Number Theory is integral to computer science and cryptography, fields that grow in importance year on year.

Mathematics is the Queen of the Sciences and Number Theory is the Queen of Mathematics.
Carl Friedrich Gauss

Just to lay out some of the notation I will be using. $\mathbb{Z}$ denotes the set of integers (whole numbers), $\mathbb{N}$ denotes the set of natural numbers (counting numbers). $a\in \mathbb{Z}$ means that a belongs to the set of integers, i.e a is an integer (whole number).

I also want to discuss what “if and only if” means as I will be using this phrase frequently. Consider the phrase “Omar eats if and only if he is hungry” this means that if “Omar eats” then “he is hungry”, and if “he is hungry” then “Omar eats”. Consider another phrase “Omar didnt get enough sleep implies that he is tired” this means that if “Omar didnt get enough sleep” then “he is tired”, but this does NOT mean that if “he is tired” then “Omar didnt get enough sleep”.

Definition 1: Divisor

Given $a,b\in \mathbb{Z}$ , we say that ‘a divides b’ or ‘a is a divisor of b’ or ‘b is a multiple of a’ or ‘a is a factor of b’ if and only if there exists $c\in \mathbb{Z}$ such that $b=ac$ . (if $a\neq 0$ this means $\frac{b}{a}\in \mathbb{Z}$ ).

Notation: ‘a divides b’ is written as a|b.

Proposition 1.1: If a|b and b|c then a|c.

Proof

If a|b then $\frac{b}{a}\in \mathbb{Z}$ which using the definition above we can write as $\frac{b}{a}=k$ where $k\in \mathbb{Z}$ from which we obtain b=ak. we have that b|c and so we can write this as ak|c. using the definition again we can say that $\frac{c}{ak}=d\in \mathbb{Z}$ which implies that $\frac{c}{a}=kd\in \mathbb{Z}$ and we get a|c as required. This is known as the Transitivity property of divisibility.

QED

Proposition 1.2: If a|b and a|c then $a|(xb \pm yc)$

Proof

Since a|b and a|c there exists $m,n\in \mathbb{Z}$ such that b=an and c=am. For any $x,y\in \mathbb{Z}$ we have $xb \pm yc = xan\pm yam = a(xn\pm ym)$ so we have found an integer $xn \pm ym$ such that $xb\pm yc=aq$ . Thus $a|(xb\pm yc)$ as required. This is known as the linearity property of divisibility.

QED

Definition 1.2: Prime and Composite Numbers

A number $p\in \mathbb{N}$ with $p>1$ is prime if and only if its only divisors are 1 and p.
A number $n\in \mathbb{N}$ with $n>1$ is composite if and only if it is not prime. (i.e n=ab for some $a,b \in \mathbb{N}$ with $a,b>1$ )

Note: n=1 is neither prime nor composite.

Before we arrive at our next result, I will breifly explain the method of proof we will employ in order to prove the validity of our result.

Proof By Induction is a method of proof used to prove statements that hold for the natural numbers ( $\mathbb{N}\in \{1,2,3,4,...\}$ ) and consists of 2 steps; The base case and the inductive step. The base case is the step in which we prove the statement is true for a value of n (usually n=1) . The inductive step is the step in which we link this base case to the rest of the natural numbers, we prove that if n=k is true then n=k+1, this forms a “ladder” constantly building and climbing infinitely up the natural numbers, proving the statement for all natural numbers.

The type of induction we will be using is called strong induction, which is closely related to the method i just described. The difference lies in the inductive step where instead of supposing that n=k is true we suppose it is true for $n\in \{1,2,3,...,k\}$ and use this to prove that it is true for n=k+1.

Proposition 1.3: If $n\in \mathbb{N}$ with $n>1$ , then n has a prime factor.

Proof:

Consider the trivial case of when n is prime, then n is a prime factor of n.

It now remains to show that the statement holds for composite numbers. We employ strong induction i.e we want to show that if for all $m\in \mathbb{N}$ with $1<m<n$ , m has a prime factor (this statement is known as the inductive hypothesis) then n has a prime factor. The base case is satisfied by showing it was true for the primes i.e we have for n=4, and 1<m<4 that m is prime and the statement holds, this forms the beginning of our ladder to extend to the rest of the natural numbers. If n is composite then n=ab where $a,b\in \mathbb{N}$ with $a,b>1$ (using our definition of composite). Clearly $1<a<n$ and by the inductive hypothesis we have that a has a prime factor i.e there exists a prime p with p|a. So we have that p|a and a|n which by the transitivity property of divison implies that p|n and we have shown that n has a prime divisor.

QED

We will use another method of proof to prove our final result. Proof by contradiction essentially works by showing that assuming the statement is false leads to a contradiciton, proving the falsehood of assuming the statement was false and therefore proving the statement is true.

Theorem 1.1: There are infinitely many prime numbers.

Proof:

Let us assume for contradiciton that there are finitely many prime numbers, i.e assuming that the set $S=\{p_{1},p_{2},...,p{n}\}$ is a complete list of primes. Consider $N=1+p_{1}\times p_{2}\times ... \times p_{n}$ clearly by construction we have that N>1. By proposition 2, N has a prime factor p, p|N. However, every prime is supposedly one of $p_{1},p_{2},...,p{n}$ , so $p=p_{i}$ for some $i\in \{1,2,...,n\}$ . Therefore $p|(p_{1}\times p_{2}\times ... \times p_{n})$ , so p|(N-1). Since we have that p|N and p|(N-1) by the linearity of divisibility (proposition 2) we have p|1 since 1=N-(N-1) which is a contradiction.