5.3　算术基本定理

5.3　算术基本定理

每个大于1的正整数n均有因子1和n，其他正因子均叫n的真因子。例如，4有真因子2，而3没有真因子。如果d是n的真因子，则n=cd，易知c也是n的真因子，n就分解成两个正整数之积，并且1＜c，d＜n。如果c或者d还有真因子，由这种分解再继续下去，一直到n=n1n2…nr，而每个ni均没有真因子时为止。所以，对于正整数的分解来说，那些没有真因子的正整数是不能再分解的“基石”。

定义　设p为大于1的正整数，如果p没有真因子（只有1和p是p的正因子），则p叫作素数（或质数），否则便叫作合数。

于是，正整数共分成三大类：1，素数，合数。

100以内的素数有25个：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89和97。

若p为素数，n为任意整数，则由素数定义不难看出：

素数的另一个重要性质是：

引理　设p是素数而a1，a2，…，an为整数，如果p|a1a2…an，则p必除尽某个ai（1≤i≤n）。

算术基本定理　每个大于1的正整数n均可分解成有限个素数之积，并且若不计素因子的次序，这个分解式是唯一的。

注记　将n的分解式中相同素因子收集在一起，可知每个大于1的正整数均可唯一写成

其中p1，p2，…，pr是彼此不同的素数，而e1，e2，…，er均为正整数，这叫作n的标准分解式。例如，4200=23·3·52·7。

如果有了正整数a，b的素因子分解式，就很容易写出它们的最大公约数和最小公倍数。