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_is divides and is thus equal to one of the q_is. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s