An extremely important theorem in Number Theory is the Fundmental Theorem of Arithmetic which states that every composite number can be written as the product of powers of primes. Other than being a bit of a tongue-twister, it's a really powerful idea.
First of all, a prime number, \(p\), is defined as a number which is only divisible by \(1\) and itself,
\[ 1\vert p \text{ and } p \vert p \,.\]A composite number, \(n\), is defined as a number which is not prime. And in fact, since composite numbers have factors or divisors other than \(1\) and themselves, they must be composed of something.
Just thinking about this logically, suppose we have the number \(60\). It turns out that I can write \(60\) in a lot of different ways,
\[\begin{aligned} 60 &= 1 \cdot 60 \\ &= 2 \cdot 30 \\ &= 3 \cdot 20 \\ &= 4 \cdot 15 \\ &= 5 \cdot 12 \\ &= 6 \cdot 10 \\ \end{aligned}\]So, I can write \(60\) in a variety of ways, but which one is the right way? Let's take \(6\) and \(10\) for instance. Given the definition of a prime number, clearly both \(6\) and \(10\) have more factors than \(1\) and themselves, so both must be composite. I can therefore factor \(6\) into \(2 \cdot 3\) and I can factor \(10\) into \(2 \cdot 5\).
Putting these together, I can write \(60\) as,
\[ 60 = 2\cdot 2\cdot 3 \cdot 5 \,\]What if I were to propose that every single one of the different ways I can write \(60\) above in \((2)\), I can write using the four factors of \(60\) found in \((3)\)?
Clearly \(2\cdot 2\cdot 3 = 12\) and \(5\) is \(60\). Additionally, \(2\cdot 2\) is \(4\) and \(3\cdot 5 = 15\). We also know that \(2\cdot 2\cdot 5 = 20\) and \(3\) is \(60\). Finally \(2\cdot 3\cdot 5 = 30\) and \(2\) is \(60\). Therefore, it turns out that of all these different ways I can write \(60\), they're really just different combinations of the four factors \(2\), \(2\), \(3\), and \(5\). So, if want to know what is right way to write \(60\), we could say that it is,
\[ 60 = 2^2 \cdot 3 \cdot 5 \,.\]This is a really powerful idea because it means that there are these fundamental numbers which are kind of like atoms in chemistry where every number which isn't an atom itself is formed from a unique combination of other atoms. These "atoms" are the prime numbers and it turns out that every composite number can be written as a unique combination of powers of primes. We'll box each prime number with a white background and each composite with a grey background as we write the numbers from \(2\) to \(20\) and their unique factors.
\[\begin{aligned} \boxed{2} &= 2 \\ \boxed{3} &= 3 \\ \colorbox{#ccc}{4} &= 2^2 \\ \boxed{5} &= 5 \\ \colorbox{#ccc}{6} &= 2 \cdot 3 \\ \boxed{7} &= 7 \\ \colorbox{#ccc}{8} &= 2^3 \\ \colorbox{#ccc}{9} &= 3^2 \\ \colorbox{#ccc}{10} &= 2\cdot 5 \\ \boxed{11} &= 11 \\ \colorbox{#ccc}{12} &= 2^2 \cdot 3 \\ \boxed{13} &= 13 \\ \colorbox{#ccc}{14} &= 2 \cdot 7 \\ \colorbox{#ccc}{15} &= 3 \cdot 5 \\ \colorbox{#ccc}{16} &= 2^4 \\ \boxed{17} &= 17 \\ \colorbox{#ccc}{17} &= 2 \cdot 3^2 \\ \boxed{19} &= 19 \\ \colorbox{#ccc}{20} &= 2^2 \cdot 5 \end{aligned}\]The pattern is clear. Whenever we have a prime number, it has a single factor – itself, and whenever we have a composite number, it has a combination of prime numbers. And in fact, the Fundamental Theorem of Arithmetic is very clear that with exception of ordering, every composite number can be written as a unique combination of powers of primes,
\[n = p_1^{q_1}\cdot p_2^{q_2}\cdot \cdots \cdot p_{k-1}^{q_{k-1}}\cdot p_k^{q_k}\,.\]This theorem is the foundation for a proof of the infinitude of prime numbers which uses proof by contradiction.
Suppose that there is a set, \(P\), consisting of a finite number of primes such that \(|P| = k\).
\[ P = \{ p_1, p_2, \dots, p_{k-1}, p_k \}\,.\]Since every composite number consists of some combination of prime factors, then there must be some number, \(q\), which is the product of every single element of \(P\),
\[ q = \prod_{i=1}^k p_i \,.\]If we were to add one to both sides, we find ourselves with a new number,
\[ q + 1 = \prod_{i=1}^k p_i + 1 \,,\]where \(q + 1\) is either prime or composite. If \(q + 1\) is prime, then there is a prime number which isn't in our set, \(P\), therefore our set is incomplete. If \(q + 1\) is composite, then we've also got a problem because in forming \(q\) we included every single element from \(P\), but after adding \(1\), none of the factors of \(q\) are factors of \(q+1\), so there must be another prime factor which we've not included in our set.
In both cases, there is a prime missing from our set and therefore \(P\) is indeed incomplete. That being the case, suppose we add this prime into our set, \(P\), and try again. In fact, we will continually find ourselves in the same situation, thereby showing that the number of primes is infinite.