Here is an important definition.
An integer $p$ greater than 1 is called prime if the only positive divisors of $p$ are 1 and $p$. Otherwise, $p$ is called composite.
A large portion of number theory is devoted to the study of prime numbers and their properties. A big reason for this is that they are considered the building blocks for numbers. This idea is so important that the primary result concerning this is called the Fundamental Theorem of Arithmetic.
Every natural number $n \gt 1$ can be written uniquely as a product of primes.
Note here the condition that $n \gt 1$. Sometimes there is some controversy among non-mathematicians over the fact that 1 is not considered a prime number. There are a number of reasons one can give to justify this idea. The main justification is due to this theorem: if 1 were a prime number, then we could no longer say that every number has a unique prime factorization.
This idea extends to other so-called unique factorization domains, which are a kind of $\mathbb Z$-like structure in abstract algebra where every non-zero and non-unit element has a unique factorization. Here, a unit is any element $x$ where one can find an element $y$ such that $xy = 1$. Obviously, in $\mathbb N$, the only one of these is 1, but in other structures, there are more elements that have these multiplicative inverses. One example you may be familiar with are the rational numbers, $\mathbb Q$.
In the end, no matter how you slice it, 1 is not a prime number. Do not fall into the trap.
In order to prove the Fundamental Theorem of Arithmetic, we need a few helpful properties of primes. The first of these is the following very useful theorem, a result from Euclid's Elements.
If $p$ is prime, and $a,b$ are integers such that $p \mid a \cdot b$, then $p \mid a$ or $p \mid b$.
Without loss of generality, suppose $p \not \mid a$. Then $\gcd(p,a) = 1$ and there exist integers $x$ and $y$ such that $xa + yp = 1$. Then multiplying both sides by $b$, we have $$b = xab + ypb.$$ Since $p \mid ab$, let $n$ be an integer such that $ab = pn$. Then we have $$b = xab + ypb = xpn + ypb = p \cdot (xn+yb).$$ Therefore, by definition of divisibility, $p \mid b$.
Notice that this proof makes use of Bézout's lemma. Since Bézout's lemma appears about 2000 years after Euclid, it is safe to say that this is not the proof that appears in the Elements.
Now, we will prove the following lemma by using induction, which we make use of later on.
If $p, p_1, \dots, p_k$ are prime and $p \mid p_1 \cdots p_k$, then $p = p_i$ for some $i$.
We will prove this by induction on $k$, the number of primes.
Base case. In this case, $p \mid p_1$. Since $p$ and $p_1$ are both prime, it must be the case that $p = p_1$.
Inductive case. Suppose our lemma is true for $k$ and consider $p \mid p_1 \cdots p_k \cdot p_{k+1}$. By Euclid's lemma, if $p \mid a \cdot b$, then $p \mid a$ or $p \mid b$. Let $a = p_1 \cdots p_k$ and $p_{k+1} = b$. If $p \mid a$, then $p = p_i$ for some $i$ with $1 \leq i \leq k$ by our inductive hypothesis and our result holds. If $p \mid b$, then $p = p_{k+1}$ and our result holds.
Now, we're almost ready to prove the Fundamental Theorem of Arithmetic. Since the theorem claims existence and uniqueness of prime factorization, we'll prove this in two parts: first we prove the fact that we can factor numbers into primes and then show that this factorization is unique.
Every natural number $n \gt 1$ can be written as a product of primes.
We will prove that for $n \gt 1$, $n$ can be written as a product of primes via strong induction on $n$.
Base case. $n = 2$. Clearly, 2 is a product of primes because 2 itself is a prime number.
Inductive case. Let $k \in \mathbb N$. Assume that for all natural numbers $m$ with $2 \leq m \leq k$, that $m$ can be written as a product of primes. We want to show that $n = k+1$ can be written as a product of primes. There are two cases to consider.
Now, we will finish the proof of Theorem 5.2 by showing that prime factorizations are unique.
By Theorem 5.5, every natural number $n \gt 1$ has a prime factorization. Suppose that prime factorizations are not unique. Let $n$ be the smallest number that doesn't have a unique prime factorization, so $$n = p_1 \cdots p_k = q_1 \cdots q_\ell,$$ where $p_i$ is prime for $1 \leq i \leq k$ and $q_j$ is prime for $1 \leq j \leq \ell$. Clearly, $p_1 \mid n$. Then by Lemma 5.4, $p_1 = q_j$ for some $j$. Now, we divide each factorization by $p_1$. This gives us $$\frac n {p_1} = p_2 p_3 \cdots p_k = q_1 q_1 \cdots q_{j-1} q_{j+1} \cdots q_\ell.$$ But this is a smaller number with more than one prime factorization, contradicting the minimality of $n$.
The following result is another of Euclid's from the Elements. You can tell that this one is very important because out of all the results of Euclid, this one is called Euclid's Theorem.
There exist infinitely many primes.
Assume for a contradiction that there are only finitely many primes $p_1, p_2, \dots, p_k$. Consider $n = p_1 \cdot p_2 \cdots p_k + 1$. Since $n \gt p_i$ for all $i$, it cannot be a prime. Observe that for each prime $p_i$, we can write $n = q \cdot p_i + 1$ for some integer $q$.
By the Division Theorem, this means that we have a remainder of 1 when dividing $n$ by any of the primes $p_i$. Since $1 \neq 0$ and $1 \lt p_i$, it must be the case that $p_i$ does not divide $n$ for all $i$. In other words, $n$ cannot be factored into primes. But this is a contradiction of the Fundamental Theorem of Arithmetic. Therefore, our assumption that there were only finitely many primes was incorrect and there must exist infinitely many primes.