以下来源于百度搜索：
算术基本定理的最早证明是由欧几里得给出的。而以下是用现代的陈述方式去证明。 待证命题：大于1的自然数必可写成质数的乘积。用反证法：假设存在大于1的自然数不能写成质数的乘积，把最小的那个称为n。非零自然数可以根据其可除性（是否能表示成两个不是自身的自然数的乘积）分成3类：质数、合数和1。
首先，按照定义，n大于1。其次，n不是质数，因为质数p可以写成质数乘积：p=p，这与假设不相符合。因此n只能是合数，但每个合数都可以分解成两个小于自身而大于1的自然数的积。设其中a和b都是介于1和n之间的自然数，因此，按照n的定义，a和b都可以写成质数的乘积。从而n也可以写成质数的乘积。由此产生矛盾。因此大于1的自然数必可写成质数的乘积。
关于定理证明需要注意几点的有：1.（注意从两数相乘可以得一合数并且两数小于这个合数入手） 这个集合中肯定有一个最小值为n，由于根据假设所以n一定为合数，又任意大于1的合数都可以表示为两个数的乘积，又a b小于n所以不在该假设集合内（n为满足假设最小的合数），所以a. b必定可以写成质数的乘积，因为不在这个集合内！由于不在该集合内，所以只要乘积中包含质数就满足不在集合内这个条件，那么可以写成质数乘质数或者质数成合数，又合数可再分且不在该集合内，所以还可以写成质数乘质数或者质数乘合数，若还是合数那么继续分反正必须包含一个质数，又合数不可能无限分割下去，所以最后由除法定义一定是质数。于是这个最小值就可以由质数表示了。接着集合内的下一个最小值同理可证。所以这个集合内的所有元素都可以表示为质数的乘积
其实也可以这么想，如果一个数是不能表示为质数的乘积，那么就是合数乘合数，那么合数再分也不可以有质数，难道存在一直可以整除下去除了1和本身？合数一定可再分，质数才不可分，所以最终的结果肯定是质数乘质数啦，不然无限整除？合数都是由质数得到的！因为质数才不可分 ，合数必丁可分，那么某个质数肯定是某个合数的因子。想得有点多，大概就这样了。
为什么会去想到这个呢？因为再看浪潮之巅 看到了那个算法题，求无理数e出现连续10位位质数的数这可能为什么素数叫prime number的原因了吧
adj. 主要的；最好的；基本的
adv. 极好地
n. 初期；青年；精华；全盛时期
vt. 使准备好；填装
vi. 作准备
n. (Prime)人名；(英)普赖姆；(德)普里梅[网络] 春心荡漾；银行贷款的最低利率[专业] 素数 [计算机科学技术]；启动 [心理学]
自然数的定义，也就是整数，要么能整除，要么不能整除，不算1和本身，就分为素数和合数。
这重温了下自然数的知识，认识一下整数的性质。曹操草，居然超时错误，让我重码！
事情是这样的，昨天我说a或b可以表示为的乘积中可以有合数，我说合数不可能无限分割，最后必定是质数，这么说其实不正确！
因为这不正是我们要证明的么？其实这是良序原理，最后我会将良序原理贴在最后。
现证明如下：
若可以表示为质数的乘积，那么就证明了定理，如果乘积中至少含有一个合数呢，这是我接下来要说的：若存在这么一些数在一个集合中满足性质：他们可以表示为的乘积中至少有一个合数。
由于自然数是从1递增的，这个集合必定有一个满足性质的最小值。
设该值为m，m又必须为合数，所以该数可表示为两数的乘积，两数分别又小于这个合数，所以不在集合内，那么这两个数都可以表示为质数的乘积，所以该最小值不存在，以此类推下一个最小值，所以该集合为空。所以得证！
良序原理：
任何非空的非负整数集合都有一个最小的元素。首先不要把良序原理（Well-ordering principle）和良序定理（Well-ordering theorem）混淆了。良序原理的关键点在于非空和非负整数——空的集合没有元素; 包含负数或者正有理数的集合也可能没有最小数。虽然看起来很简单，但它是离散数学里最重要的原理之一。
良序原理的使用方法一般都相似。
例如，我们要证明对于所有的属于N集合的元素n，P(n)都成立：设存在集合C，C中的元素为P的反面例子，也就是说，C ::= {n belongs to N | NOT(P(n)) is true}。假设C是非空的（反证）。
由良序原理，C中会有一个最小的元素n。推出一个矛盾的结果。例如P(n)事实上是正确的，也就是说最小值不存在，或者C存在一个比n还要小的元素使得NOT(P(n))不成立等等。
得出结论，C一定是空集，即不存在属于N的元素使得P(n)不成立。算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。下面利用良序定理对其证明。
必然性：设存在集合C，C中的元素为大于1的自然数，且不能写成质数的乘积。假设C是非空的。由良序原理，C中存在一个最小的元素n，n不能写成质数的乘积。由C的性质，n不能是一个质数，因为质数分解因式只能得到本身即质数的乘积，所以n可以写成a * b。由 a > 1, b > 1，所以a < n, b < n，所以a, b不属于集合C（n是最小的元素），即a和b都可以写成质数的乘积。a = p1p2…pn, b = q1q2…qn, 所以n = p1p2…pnq1q2…qn，即n可以写成质数的乘积。矛盾。得出结论，C一定是空集，即大于1的自然数均可写为质数的积。
唯一性：设存在集合C，C中的元素为大于1的自然数，且可以以多于一种的方式写成多个质数的乘积。假设C是非空的。由良序原理，C中存在一个最小的元素n，n可以以多于一种的方式写成多个质数的乘积。同必要性证明，n不可能是一个质数，设n = p1p2…pn = q1q2…*qn，其中p序列和q序列存在不相同的值，则p1整除q序列中的一个元素qk（可以用裴蜀定理证明），由于qk也是质数，所以qk = p1，所以存在一个比n小的元素n’，使得n’ =p2…pn = q1… *qn（不包含qk），所以n‘也满足C要求的性质。矛盾。结合必然性的证明，得出结论。每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。
良序集合：如果一个实数集合的每个非空子集都有一个最小的元素，就说该集合是良序的。在计算机领域中，良序的概念经常会用来证明程序是可终止的。通常的方法是证明算法中存在一个每次成功运算后其规模都会变小的值，如果这个值属于一个良序集合，那么这个运算就是可终止的——因为如果不会终止，那么这个值就会导致良序集合存在一个没有最小值的非空子集。
在计算机算法中的应用
如果我们能把一个计算的诸状态x映射到属于良序集S的一个元素f(x)，(这相当于是良序集合的一个子集吧)且使得计算的每一步把一个状态x转换成状态y，并有f(y)<f(x),则算法必然终止。
设S对于<是良序，且设P(x)是关于S的元素x的一个命题。 求证：如果在对于所有的y < x,P(y)为真的假定下能证得P(x)为真，则P(x)对S中得所有x为真。 证明： 令A是使得P(x)为假的所有的x的集合。 如果A非空，则它含有最小的元素x0。 因此，P(y)对于所有y < x0为真。 但这意味着P(x0)为真，所以x0不在A中（与假设矛盾） 因此：A必须为空 => 即P(x)总是为真。让人迷惑的P(x)嚯哈哈哈哈哈~~
想不明白对照一下算数基本定理的证明!关键是良序呀！
对，这都是自然数，整数集
良序原理(well-ordering)
自然数集的每个非空子集都有个最小元素，即自然数在其标准的大小关系下构成一良序集在公理集合论中，自然数集定义为最小的归纳集合（包含0且包含本身中每个元素的后继的集合），
可以证明，所有满足{0,…,n}为良序集的n组成的集合是一个归纳集合，从而是自然数集本身。由此可以推出自然数集本身也是个良序集。
良序定理是选择公理的等价形式之一其内容为：对任何集合S，存在S上的二元关系R，使得<S，R>是良序集意义良序原理的意义主要在于，
在证明时可以使用所谓的“最小反例法”，它相当于反证法和数学归纳法的结合。
一般描述：设"<"是集合S上的一个关系，它满足以下性质：给定S中的x,y,和z,如果 x<y 和 y<z,则 x<z;给定S中的x和y，以下三种可能中恰有一种为真：x<yx=yy<x如果A是S的任何非空子集，则A中有一个元素x，使得对于A中所有的y，有x<=y（即x<y或x=y）这个关系被称为S的一个良序关系
