Sheng Li (gmachine1729) wrote,
Sheng Li
gmachine1729

Proof of fundamental theorem of arithmetic

Originally published at 狗和留美者不得入内. You can comment here or there.

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.

Tags: number theory, 数学/математика
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

  • 0 comments