Prime Numbers

Definition

A natural number $n > 1$ is composite if there exists natural numbers $m$ and $k$, not necessarily distinct, both smaller than $n$ and satisfying

\[ n = m\cdot k \]

A number greater than 1 which is not composite is called prime. In other words, a prime number is number greater than 1 which is not the product of two smaller numbers.

Throughout this sheet, the term “number” refers to an element of the set $\N $. In other words, we exclude the natural number 0.

Examples

The first few primes. Since the only number smaller than $2$ is $1$ and $2 \neq 1\cdot 1$, $2$ is the first and smallest prime. Likewise, $3 \neq 1\cdot 2$, $3 \neq 1\cdot 1$, $3 \neq 2\cdot 2$. So $3$ is the second smallest prime.

The first composite. Now consider $4$. Since $4 = 2\cdot 2$ and $2 \leq 4$, 4 is the smallest composite number.