I was trying to think of another way of showing that there are an infinite number of primes. I came up with the following argument, but I am not sure if it is valid. I don't know how to make it more formal (I'm not a mathematician). The basic approach I'm attempting is to assume that there are a finite number of primes, and then to show that a finite set of prime numbers cannot be combined to produce every natural number in some arbitrary set of natural numbers. Thus, some natural numbers would be neither prime nor composite, but since every natural number is in fact either prime or composite, this creates a contradiction and thus there are infinite primes.
Let $P$ be the set of all primes $\{2,3,5,...p_m\}$ and let $S$ be the set of all natural numbers between $1$ and $p_m^n$ (i.e. $\{1,2,3,...,p_m^n\}$), where $n$ is a natural number. Note that $P$ is a subset of $S$. Every element of $S$ is either prime, or can be written as a product of primes. We can think of each number in $S$ as a product of every prime in $P$, each raised to an exponent of $\ge0$. For instance, $10=2^1*3^0*5^1*7^0*11^0*...p_m^0$.
Let $a$ be a whole number such that $2^a < p_m^n$ and $2^{a+1}>p_m^n$. In other words, $a$ is the greatest power of $2$ that is smaller than $p_m^n$. Since exceeding the power of $a$ for the smallest prime would be greater than $p_m^n$, it follows that any other prime number raised to a power $>a$ would also exceed $p_m^n$. This sets the upper bound for exponents in the prime factorization of any element of $S$, therefore the prime factorization of any element of $S$ will contain only powers of primes $\le a$.
Every element of $S$ can therefore be written as $2^{q_1}*3^{q_2}*5^{q_3}*...*p_m^{q_m}$, where $0\le q \le a$. Let $C$ be the set of every possible combination of the above. Since there are $m$ primes, and each prime can have an exponent from $0$ to $a$, there are therefore $(a+1)^m$ numbers that can be generated in this way (these numbers include composite and prime numbers, since the primes are formed when a single prime has a power of $1$ and every other prime has a power of $0$). Note, $S$ must be a subset of $C$ since every element of $S$ can be represented in this way, but $C$ contains elements that are clearly $> p_m^n$ and thus those elements are not in $S$, i.e. $p_m^a$ where $a$ is clearly larger than $n$. Since $S$ is a subset of $C$, then $S$ must have fewer elements than $C$:
1) $|S| < |C|$
since $|S| = p_m^n$ and $|C| = (a+1)^m$
2) $p_m^n < (a+1)^m$
If the above statement is true, then replacing $a+1$ with a value greater than $a+1$ should also be true. Since $2^a<p_m^n$ by definition, multiplying both sides by 2 gives:
$2^{a+1}<2p_m^n$
Taking the $log_2$ of both sides:
$a+1<log_2(2p_m^n)$
$a+1<log_2(2) + nlog_2(p_m)$
$a+1<1+nlog_2(p_m)$
Now replacing $a+1$ in equation 2) with $1+n*log_2(p_m)$:
$p_m^n < [1+n*log_2(p_m)]^m$
Clearly if this inequality holds for any value of $n$, it does not do so for all values of $n$. The left side grows exponentially as $n$ increases. The right side is a polynomial of the form $(1+bn)^m$ where $b$ and $m$ are constants. Thus for sufficiently large $n$, the inequality fails. Since the inequality is false for at least some values of $n$, then $|S|$ must be sometimes larger than $|C|$, which means there must exist elements of $S$ that are not contained within $C$. These element would be neither prime, nor composite. However, all natural numbers must be either prime or composite, thus there exists a contradiction and the proposition that there are a finite number of primes must be false.
I challenged myself to construct a proof that there are infinite primes before looking at any existing solutions. I have since looked, and while this is not very elegant, I wonder if it is actually valid. I would appreciate any feedback.
Apart from some minor details ($0$ to $a$ is $a+1$ different exponents so there are actually $(a+1)^m$ numbers in $C$, like you commented yourself), this seems correct, but unnecessarily complicated as anything but a purely intellectual exercise in creating proofs and familiarising oneself with natural numbers, primes and factorisations of natural numbers..