Below is a simple conceptual proof of Bezout's identity for the gcd.
The set $\rm\:S\:$ of all integers of form $\rm\:a\:x + b\:y,\,\ x,y\in \mathbb Z,\:$ is closed under subtraction so, by Lemma below, every positive $\rm\:n\in S\:$ is divisible by $\rm\:d = $ least positive $\rm\in S,\:$ so $\rm\:a,b\in S\:$ $\Rightarrow$ $\rm\:d\:|\:a,b.\:$ Thus $\rm\:d\:$ is a common divisor of $\rm\:a,b,\:$ necessarily greatest, $ $ by $\rm\:c\:|\:a,b\:$ $\Rightarrow$ $\rm\:c\:|\:d = a\:x\!+\! b\:y\:$ $\Rightarrow$ $\rm\:c\le d.$
Lemma $\ $ If a nonempty set of positive integers $\rm\: S\:$ satisfies both $\rm\ n > m\: \in\, S \ \Rightarrow\ n-m\, \in\, S$
then every element of $\rm\:S\:$ is a multiple of the least element $\rm\:m_{\circ} \in\, S.$
Proof $\,\bf 1$ $\ $ If not there is a least nonmultiple $\rm\:n\in S,\,$ contra $\rm\:n-m_{\circ} \in S\:$ is a nonmultiple of $\rm\:m_{\circ}$
Proof $\,\bf 2$ $\rm\ \ S\,$ closed under subtraction $\rm\:\Rightarrow\:S\,$ closed under remainder (mod), when it is $\ne 0,$ since mod may be computed by repeated subtraction, i.e. $\rm\: a\ mod\ b\, =\, a - k b\, =\, a-b-b-\cdots -b.\:$ Hence $\rm\:n\in S\:$ $\Rightarrow$ $\rm\: n\ mod\ m_\circ = 0,\:$ else it is $\rm\,\in S\,$ and smaller than $\rm\:m_\circ\,$ contra mimimality of $\rm\:m_\circ$
Remark $\ $ In a nutshell, two applications of induction yield the following inferences
$$\!\rm\begin{eqnarray} S\ closed\ under\ subtraction &\!\Rightarrow\:&\rm S\ closed\ under\ mod \!=\! remainder = repeated\ subtraction \\
&\!\Rightarrow\:&\rm S\ closed\ under\ gcd\! =\! repeated\ remainder\!\!: Euclid'\!s\ algorithm \end{eqnarray}$$
Interpreted constructively, this yields the extended Euclidean algorithm for the gcd. Namely, $ $ starting from the two elements of $\rm\,S\,$ that we know: $\rm\ a \,=\, 1\cdot a + 0\cdot b,\ \ b \,=\, 0\cdot a + 1\cdot b,\ $ we search for the least element of $\rm\,S\,$ by repeatedly subtracting elements to produce smaller elements of $\rm\,S\,$ (while keeping track of every elements linear representation in terms of $\rm\,a\,$ and $\rm\,b).\:$ This is essentially the subtractive form of the Euclidean algorithm (vs. the mod/remainder form).
Here's a proof of the uniqueness of FTA by induction that is different from the proof you cite from Wikipedia. It is due to Zermelo, and isn't as widely known as the other proofs.
Suppose we already proved uniqueness for all numbers $<n$ and are now proving for $n$. If $n$ is prime, there is nothing to prove. Otherwise let $p$ be the smallest divisor of $n$ that is not 1. Clearly $p$ must be prime, otherwise it would not be the smallest.
We claim that any way to write $n$ as a product of primes must include $p$. If we succeed in proving this, our work is done - why? Because if any two factorisations of $n$ must both include $p$, we can take $p$ out, get a smaller number, invoke uniqueness as the inductive assumption and see that the factorisations are really the same.
Consider any factorisation $n=q_1*q_2*\dots*q_s$. If $q_1=p$, we are done. Otherwise we can form a number $n'=p*q_2\dots*q_s$, where we replaced the first factor $q_1$ by $p$. Because $p$ is the smallest divisor, $n'$ must be smaller than $n$. Note that their difference can be written
$n-n' = (q_1-p)*q_2*\dots*q_s$
We know that $p$ divides this number $n-n'$, because it divides both $n$ and $n'$. And this number is less than $n$, so by inductive assumption it only has one factorisation, in which $p$ must participate. But look at the product above: $p$ does not divide $q_1-p$, so the only way it can participate is by being one of $q_2\dots q_s$, which is what we wanted to prove.
Best Answer
I think this is the proof of Euclid's Lemma, and then I go on to prove the Fundamental Theorem of Arithmetic, which is what I first set out to do. The first paragraph proves Euclid's Lemma, the second paragraph proves that all positive integers greater than 1 can be factored into primes, and the third paragraph proves that the factorization is unique, which is the Fundamental Theorem of Arithmetic:
Please let me know if I got anything wrong.
EDIT: I added a first paragraph, and modified the second paragraph at the point "there must be some x". The new first paragraph is VII.20, the now-second paragraph is VII.30 (Euclid's Lemma), and the third and fourth paragraphs are the Fundamental Theorem of Arithmetic.
Now is it right?