# Proof of fundamental theorem of arithmetic

I read it a couple days ago and actually remembered it this time in a way that I will never forget it. It invokes Euclid’s lemma, which states that if $p | ab$ for $p$ prime, then $p | a$ or $p | b$, which can be proved using Bezout’s lemma. For existence, it does induction on the number of factors, with $1$ as the trivial base case. For the non base case, wherein our number is composite, apply the inductive hypothesis on the factors. For uniqueness, assume two distinct factorizations: $p_1p_2\ldots p_n = q_1q_2\ldots q_n$. By Euclid’s lemma, each of the $p_i$s divides and is thus equal to one of the $q_i$s. Keep invoking Euclid’s lemma, canceling out a prime factor on each iteration and eventually we must end with $1 = 1$ in order for the two sides to be equal.