# 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)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:

- 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)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.