For a long time, I didn't know exactly how the Fundamental Theorem of Arithmetic (unique prime factorization) was proved from first principles.
I finally figured out the order of proofs for the fundamental theorem of arithmetic from first principles. Now that I know the sequence, it feels like it was my own fault for not properly going through a textbook and that it was probably obvious to everyone. I'm posting this mainly to reinforce my own clarity on the topic.
1. Well-Ordering Principle, this is either taken as axiomatic or one step away from axioms. This is where I'm drawing the line for "first principles".
2. Euclidean Division: Existence and Uniqueness of quotient 𝑞 and remainder 𝑟 in 𝑎 = 𝑞𝑏 + 𝑟 form. Uniqueness if 𝑟 between [0,1,...,𝑞−1]. Proof is just well-ordering principle (often framed as infinite descent).
3. Bezout's Identity. Proof starts with well-ordering to find 𝑑, then together with Euclidean division shows that 𝑑 is a divisor. A bit more Euclidean division shows that all other factors 𝑑' also divide 𝑑. So 𝑑 is the greatest divisor.
4. Euclid's Lemma: Proof says if 𝑝 doesn't 𝑎 in product 𝑎𝑏, then gcd(𝑎,𝑝)=1. This brings in the above and some rearrangement proves that 𝑏 is a factor as needed.
5. Fundamental Theorem of Arithmetic: Existence usually goes via strong induction (which can be rephrased as Well-Ordering + contradiction). Uniqueness uses Euclid's Lemma to show that the primes in the factorization must divide each other (which implies equality).