Theorem 12.1 (Euclid's Lemma). If $p$ is prime, and $a,b$ are integers such that $p \mid a \cdot b$, then $p \mid a$ or $p \mid b$.
Proof. 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$. $$\tag*{$\Box$}$$
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, which will allow us to prove the uniqueness part of the Fundamental Theorem of Arithmetic.
Lemma 12.2. If $p, p_1, \dots, p_k$ are prime and $p \mid p_1 \cdots p_k$, then $p = p_i$ for some $i$.
Proof. 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 Theorem 12.1, 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. $$\tag*{$\Box$}$$
Proof of the Fundamental Theorem of Arithmetic (Uniqueness).
Claim: $\forall~a,p_1,p_2,\dots,p_n,q_1,q_2,\dots q_m$ where every $p_i$ and $q_i$ is prime, if $$a = p_1p_2\dots p_n = q_1q_2 \dots q_m$$ then the $p_i$s and $q_i$s are the same (that is, they form the same multiset).
We'll prove this by induction on $n$.
Our base case is where $n=1$. Since $p_1$ is prime, there can only be one $q_i$ and $q_i$ must equal $p_i$.
For the inductive case assume for all $a$, $p$s and $q$s, we have $a = p_1p_2\dots p_k = q_1q_2 \dots q_m$ implies the $p_i$s and $q_i$s are the same. Consider $a' = p_1p_2\dots p_kp_{k+1} = q_1q_2 \dots q_m$. Since $p_{k+1}$ divides $q_1q_2 \dots q_m$, there must be some $p_j$ such that $p_j = p_{k+1}$ by lemma 12.2. By our inductive hypothesis, $p_1p_2\dots p_k = q_1q_2 \dots q_{j-1}q_{j+1}q_m$ implies the $p_i$s and $q_i$s are identical. Hence multiplying both by $p_k+1 = q_j$ preserves the identity and demonstrates uniqueness.
Alternative Proof via minimality: We showed that 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 12.2, $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$. $\tag*{$\Box$}$
Theorem 12.3 (Euclid's Theorem). There exist infinitely many primes.
Proof. 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. $\tag*{$\Box$}$
The following is an instance of the Frobenius problem, due to Ferdinand Frobenius in the late 1800s. In general, the Frobenius problem asks, given positive relatively prime integers $x_1, x_2, \dots, x_n$, what is the largest integer not representable as a non-negative integer linear combination of the $x_i$.
We can think of this as a currency denomination problem. In the US, pennies are still in use, so every integer is representable, since we can just fill in the gaps with the 1 cent coins. However, in Canada, the penny was eliminated in 2012 and the smallest coin that is still minted is the nickel, which is 5 cents. Combined with the fact that the other coin denominations are 10 and 25 cents, this means that no integer number of cents that is not divisble by 5 can be represented (which is why we require relatively prime integers).
Theorem 11.7. Every natural number $n \geq 12$ can be written as $n = 4a + 5b$ for $a,b \in \mathbb N$.
Proof. We will prove this by induction on $n$.
Base case. For $n = 12$, we observe that $12 = 4 \cdot 3$.
Inductive case. Let $k \in \mathbb N$ be arbitrary with $k \geq 12$ and assume $k = 4a + 5b$ for $a,b \in \mathbb N$. Consider $n = k+1$. There are two cases to consider.
We can also prove this via strong induction. Recall that strong induction says that for a statement $P(n)$, if
are both true, then the following is true:
Proof. We will prove this by strong induction on $n$.
Base case. We will show that this is true for $n = 12, 13, 14, 15$. We have \begin{align*} 12 &= 4 \cdot 3 + 5 \cdot 0, \\ 13 &= 4 \cdot 2 + 5 \cdot 1, \\ 14 &= 4 \cdot 1 + 5 \cdot 2, \\ 15 &= 4 \cdot 0 + 5 \cdot 3. \end{align*}
Inductive case. Let $k \in \mathbb N$ be arbitrary with $k \geq 15$ and assume for all $12 \leq j \leq k$ that $j = 4a + 5b$ for some $a,b \in \mathbb N$. Consider $n = k+1$. Since $k \geq 15$, we have that $k - 3 \geq 12$ and $k-3 = 4a + 5b$ with $a,b \in \mathbb N$. Then $k+1 = 4(a+1) + 5b$. $\tag*{$\Box$}$
You can find the proof of this in the Rosen textbook, where the question is formulated in terms of stamps and stamp denominations. This is not a perfect analogy like the coin formulation of the problem because an envelope has a finite amount of space for you to place stamps. This leads to a variant of the problem, where you also limit the number of stamps you can use.
Another instance of the Frobenius problem was formulated as a question not about coins, but about boxes of McNuggets. At the time the problem was posed, McNuggets came in boxes of 6, 9, and 20 in the UK, which is where Picciotto, who posed the problem, was from. So if you wanted to, say, split a bunch of nuggets evenly between seven people, you had to get at least 35 nuggets because there would be no way to get 7, 14, 21, or 28. It turns out that 43 is the smallest non-representable number.
Theorem 11.8. Every natural number $n \geq 44$ can be written as $n = 20a + 9b + 6c$ for some $a,b,c \in \mathbb N$.
Proof. We will prove this by strong induction on $n$.
Base case. We will show that this is true for $n = 44, 45, 46, 47, 48, 49$. We have \begin{align*} 44 &= 20 \cdot 1 + 9 \cdot 0 + 6 \cdot 4 \\ 45 &= 20 \cdot 0 + 9 \cdot 3 + 6 \cdot 3 \\ 46 &= 20 \cdot 2 + 9 \cdot 0 + 6 \cdot 1 \\ 47 &= 20 \cdot 1 + 9 \cdot 3 + 6 \cdot 0 \\ 48 &= 20 \cdot 0 + 9 \cdot 0 + 6 \cdot 8 \\ 49 &= 20 \cdot 2 + 9 \cdot 1 + 6 \cdot 0 \\ \end{align*}
Inductive case. Let $k \in \mathbb N$ be arbitrary with $k \geq 50$ and assume for all $44 \leq j \leq k$ that $j = 20a + 9b + 6c$ for some $a,b,c \in \mathbb N$. Consider $n = k+1$. Since $k \geq 50$, we have that $k - 6 \geq 44$ and therefore $k-6 = 20a + 9b + 6c$ with $a,b,c \in \mathbb N$. Then $k+1 = 20a + 9b + 6(c+1)$. $\tag*{$\Box$}$
Nowadays, nuggets don't come in odd-numbered denominations, at least not in the US or Canada.