# 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_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.

Tags:
• #### 中国姓氏的南北分布

有意思的是分布是很不均匀的，也就是说好多姓是南方比例远高于北方比例或相反。从这一点，你如果知道一个人的父母的姓氏，你就可以对他是北方人还是南方人有个有点统计显著的估计。 读者可以在包含大姓分布图的…

• #### 我反驳斯坦福大学物理教授祁晓亮发表在他脸书上的政治言论

包含其截屏链接： 祁晓亮的脸书政治言论 关于斯坦福反华反g及今年丑闻事件的知乎文章 在以上链接的知乎文章，有评论问为什么我认为祁晓亮是反华反g的。在这里我把他的脸书内容一个一个地分析反驳而解释。…

• #### Why I think Stanford professor James Landay's piece on computing in China in 2011 exposed his idiocy

I dittoed his blog post on my LiveJournal too, see https://gmachine1729.livejournal.com/175023.html. For the original, see…

• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic