Prime and Composite Numbers

Prime Numbers

Definition: An integer $p > 1$ is said to be Prime if the only divisors of $p$ are $\pm 1$ and $\pm p$.

For a long time it was debated whether the number $1$ should be classified as a prime number or not. The importance of $1$ being classified as a prime number was uninteresting and so the first prime number is officially $2$.

If $\mathbb{P}$ is the set of all prime numbers, then the first few primes in $\mathbb{P}$ are:

(1)

\begin{align} \quad \mathbb{P} = \{2, 3, 5, 7, 11, 13, ... \} \end{align}

We will now look at a very simple theorem that says the greatest common divisor between an integer $a$ and any prime $p$ is either $1$ or $p$ depending on whether $p$ divides $a$.

Theorem 1: If $a, p \in \mathbb{Z}$ and $p$ is a prime number then $\gcd (a, p) = 1$ if $p \not \mid a$ or $\gcd (a, p) = p$ if $p \mid a$.

• Proof: Since $p$ is prime, the only positive divisors of $p$ are $1$ and $p$ so $\gcd (a, p) = 1$ if $p \not \mid a$ or $\gcd (a, p) = p$ if $p \mid a$. $\blacksquare$

One important aspect of prime numbers is that every integer $n > 1$ is divisible by a prime number $p$ which we prove in the following lemma.

Lemma 1: If $n \in \mathbb{Z}$ and $n > 1$ then there exists a prime $p \in \mathbb{P}$ such that $p \mid n$.

Lemma 1 also holds if $n \in \mathbb{Z}$ and $n < 1$ and can be proven in an analogous manner. Furthermore, if $n = 0$ then every number divides $0$ and by extension, every prime $p \in \mathbb{P}$ divides $0$.

• Proof: Let $S$ be the set of positive divisors of $n$, that is:

(2)

\begin{align} \quad S = \{ d \in \mathbb{Z} : d \mid n \} \end{align}

• The set $S$ is nonempty since $1, n \in S$. If $1$ and $n$ are the only elements in $S$ then this implies that $n$ is prime and so $p = n$ divides $n$. If there exists more elements in $S$, then since $S \setminus \{1 \}$ is a nonempty subset of integers we have that by The Well-Ordering Principle of the Natural Numbers that a least element $d$ exists in $S \setminus \{ 1 \}$.

• There are two subcases to consider. If $d_1$ is prime then $p =d_1$ and $d_1 \mid n$. If $d_1$ is not prime then there exists a positive divisor $d_2$ of $d_1$, so $1 < d_2 < d_1 < n$. But this implies that $d_2 \in S \setminus \{ 1 \}$ and $d_2 < d_1$, which is a contradiction since $d_1$ is the least element in $S \setminus \{ 1 \}$. Therefore $d_1$ is actually prime and again, $d_1 \mid n$.

• Therefore if $n > 1$ then there exists a prime $p \in \mathbb{P}$ such that $p \mid n$. $\blacksquare$

Composite Numbers

Definition: An integer $n \geq 1$ is said to be Composite if it is not prime, that is, there exists a $d \in \mathbb{Z}$, $1 < d < n$ such that $d \mid n$ OR $n = 1$.

For example, the numbers in the following set are composite:

(3)

\begin{align} \quad \{4, 6, 8, 9, 10, 12, ... \} \end{align}

One important aspect of composite numbers is that every nonnegative even number (except $2$) is composite since all of such numbers has $2$ as a nontrivial divisor.