Primes Numbers

Definition: A Prime Number is an integer $p \geq 2$ whose only positive divisors are $1$ and $p$.

For example, the first few prime numbers are:

(1)

\begin{equation} 2, 3, 5, 7, 11, 13, 17, 19 ... \end{equation}

The fact that prime numbers have only $1$ and $p$ as their divisors allow them to have some nice properties in and of themselves as well as with the rest of the integers. We will look at some elementary lemmas and theorems regarding primes now.

Lemma 1: Every integer $n > 1$ is divisible by a prime.

• Proof: Let $S$ be the set of divisors of positive divisors of the integer $n > 1$. This set is clearly nonempty by the fact that for any integer $n$ has $1$ and $n$ as positive divisors.

• Hence, $S$ is bounded below by $1$. By the Well-Ordering principle there must be a smallest element of $S$, call it $d \in S$ where $d \leq s$ for all $s \in S$. If $d$ is prime then we are done.

• Instead suppose that $d$ is not prime. Then $d$ can be written as a product of two positive numbers $s$ and $t$ where $s, t > 1$, that is:

(2)

\begin{equation} d = st \end{equation}

• Since $s, t > 1$ we must have that $s < d$. Furthermore, $s \mid d$. But since $s \mid d$ and $d \mid n$ we must have that $s \mid n$. So $s > 1$ is a positive divisor of $n$. Therefore $s \in S$ and $s < d$ contracting $s$ being the smallest positive divisor of $n$. Therefore $d$ is a prime divisor of $n$. $\blacksquare$

The next theorem is a famous theorem that is often described as one of the most beautiful proofs in mathematics as the proof itself relies only on simple logic and basic number theory concepts.

Theorem 1 (Euclid's Theorem): There exists infinitely many primes.

• Proof: Suppose instead that there are finitely many primes. Then we can list these primes out as $p_1, p_2, ..., p_n$. Consider the number $N > 1$ as the product of all these primes plus $1$, that is:

(3)

\begin{align} \quad N = p_1p_2p_3...p_n + 1 \end{align}

• Clearly $N > 1$, so by Lemma 1 we have that $N$ has a prime divisor, $q$. So $q \mid N$. So $p_1, p_2, ..., p_n$ is a list of all primes we also have that $q \mid p_1p_2...p_n$. Since $q$ divides two of the three terms in the equation above, we must also have that $q \mid 1$. But all primes $q$ are greater than $2$, so $q \mid 1$ which is a contradiction.

• Therefore our assumption that there were finitely many primes must have been false. Hence there are infinitely many primes. $\blacksquare$

Theorem 2: Every integer $n > 1$ can be written as a product of prime numbers.

• Proof: Let $n > 1$ be an integer. Then by Lemma 1 we have that $n$ has a prime divisor, say $p_1$. Then $n$ can be written in the form:

(4)

\begin{equation} n = p_1n_1 \end{equation}

• Now if $n_1 = 1$ then $n = p_1$ in which $n$ is written as a trivial product of a single prime. If $n_1 \neq 1$ then $n_1 > 1$ and we can apply Lemma 1 again which says that $n_1$ has a prime divisor $p_2$ such that:

(5)

\begin{equation} n_1 = p_2n_2 \end{equation}

• If $n_2 = 1$ then $n_1 = p_2$ and $n = p_1p_2$. If $n_2 \neq 1$ then $n_2 > 1$ and Lemma 1 can be applied again. We have that $n > n_1 > n_2 > ...$ and this sequence of positive integers and is bounded blow by $1$ and must hence must terminate eventually. Therefore $n$ can be written as a product of primes. $\blacksquare$

Theorem 3: If $p$ is a prime number and $p \mid ab$ then $p \mid a$ or $p \mid b$ or both.

• Proof: Suppose that $p \mid ab$. Since $p$ is prime we have that $(a, p) = 1$ or $(a, p) = p$. If $(a , p) = p$, then $p \mid a$. If $(a , p) = 1$, then we must have that $(b, p) = p$ and so $p \mid b$. $\blacksquare$