§1.3算术基本定理 定理1任一整数n>1都可以表示成素数的乘积,且 在不考虑乘积顺序的情况下,该表达式是惟一的。即 n=PP2…P,P≤P2≤…≤p (1) 其中p是素数。并且若有 n=q1q2…q,q≤q2 其中q是素数,则 S,p=q,1≤i≤r 证由第一节定理2(1)式对所有大于1的整数m都 成立,下证惟一性。设还有 n=q1q2…q,qsq2 其中q是素数,则 P1P2…P=qq2∵q (2) 因此pqg…q,根据1.2例4,存在q使得p|q 但p,q都是素数,故p=q 同理可证存在p使得p=q,即有 pi sp =q,sq=p 所以P=q。将(2)式的两端同时消除p,则有 P2…P=q2q 同理可以推出p2=q2,依次类推得到 s,p=q 1<i 把式(1)中相同的素数合并,即得
§1.3 算术基本定理 定理 1 任一整数 n 1 都可以表示成素数的乘积，且 在不考虑乘积顺序的情况下，该表达式是惟一的。即 n = p1 p2 pr ， p1 p2 pr （1） 其中 i p 是素数。并且若有 n = q1q2 qs ， q1 q2 qs 其中 j q 是素数，则 r s p q i r = , i = i , 1 。 证 由第一节定理 2（1）式对所有大于 1 的整数 n 都 成立，下证惟一性。设还有 n = q1q2 qs ， q1 q2 qs 其中 j q 是素数，则 p1 p2 pr = q1q2 qs （2） 因此 p1 q1q2 qs | ，根据 1.2 例 4，存在 j q 使得 p qj | 1 ， 但 p qj , 1 都是素数，故 p1 = qj 同理可证存在 k p 使得 pk = q1 ，即有 p1 pk = q1 qj = p1 所以 p1 = q1 。将（2）式的两端同时消除 1 p ，则有 p2 pr = q2 qs 同理可以推出 p2 = q2 ，依次类推得到 r s p q i r = , i = i , 1 把式（1）中相同的素数合并，即得
n=pp P.sp p (3) 称(3)式为整数n的标准素因数分解式。 应用上一节性质2(ⅴ)关于整除的性质可以得到如 下推论 推论1设整数n由(3)式给出。那么d是n的正因数的 充分必要条件是 d=pp2…p,0≤d,≤a,1≤i≤s(4 从而整数n的正因数的个数为 d(m)=(1+a1+a)…(1+a) 推论1告诉我们:只要知道了正整数的标准分解式, 它的所有正约数就全知道了,且由等式(4)给出 例1设n|ab,n|cd,n|(ac+bd),证明: n ac,n 在实际应用中,为了简便,我们经常使用整数n素因数 分解如下的形式 =Pp2…p,p≤p2≤…≤p,α≥0,i=1,2,…S 它与(3)式的区别是允许某些a=0,很明显这种分 解方法不是惟一的,有了这种分解形式,我们很容易 得到如下关于最大公因数和最小公倍数的求解方法。 推论2设整数a,b有如下素因数分解形式 a=P"p"…P,b=P"P 0≤a,B,=1,2 (5)
s n p p ps 1 2 = 1 2 ， p1 p2 ps ， i s i 0, =1,2, , （3） 称（3）式为整数 n 的标准素因数分解式。 应用上一节性质 2（ⅴ）关于整除的性质可以得到如 下推论 推论 1 设整数 n 由（3）式给出。那么 d 是 n 的正因数的 充分必要条件是 ds s d d d p p p 1 2 = 1 2 ， 0 di i ， 1 i s （4） 从而整数 n 的正因数的个数为 ( ) (1 )(1 ) (1 ) d n = +1 +2 + s 推论 1 告诉我们：只要知道了正整数的标准分解式， 它的所有正约数就全知道了，且由等式（4）给出。 例 1 设 n | ab,n | cd,n | (ac + bd) ，证明： n | ac,n | bd 。 在实际应用中，为了简便，我们经常使用整数 n 素因数 分解如下的形式 s n p p ps 1 2 = 1 2 ， p1 p2 ps ， i s i 0, =1,2, , 它与（3）式的区别是允许某些 i = 0 ，很明显这种分 解方法不是惟一的，有了这种分解形式，我们很容易 得到如下关于最大公因数和最小公倍数的求解方法。 推论 2 设整数 a,b 有如下素因数分解形式 s a p p ps 1 2 = 1 2 ， s b p p ps 1 2 = 1 2 ， i s i i 0 , , =1,2, , （5）
记=m(a,B),δ=max(a,B),i=1,2,…,s,则有 (a,b)=pp2…p,[a,b]=p3p2…p 进一步由恒等式a+B=mn(a,B)+max(a,B)有 ab=(a, bla, 6] 例2设ab,c都是正整数,则有 (a, b(a,c(b, cla,b,c]=abc(a, b 利用整数的惟一分解式,可以得到如下结果,这一结 果将用于高次剩余中原根的构造 例3设a,b是两个正整数,则存在正整数a',b,满足 aa, bb, (a,b)=l,a'b=[a,b §1.4习题 1.设p是正整数n的最小素因数,证明:若p>n n/p是素数 2.设n≠1。证明:(n-1)|(m2-1)的充要条件是 3.证明对于一切整数,n2+2n+12都不是121的倍数。 4证明:(1)24|n(n+1)n+2)mn+3);(2)30n2-n 5.证明对于任意整数n,_n+n3+′n是整数。 6.证明:当n为大于1的正整数时 S=1+
记 min( , ) i i i = ， max( , ) i = i i ， i =1,2, ,s ，则有 s a b p p ps 1 2 1 2 ( , ) = ， s a b p p ps 1 2 1 2 [ , ] = 进一步由恒等式 + = min(,) + max(,) 有 ab = (a,b)[a,b]。 例 2 设 a,b,c 都是正整数，则有 (a,b)(a,c)(b,c)[a,b,c] = abc(a,b,c) 利用整数的惟一分解式，可以得到如下结果，这一结 果将用于高次剩余中原根的构造。 例 3 设 a,b 是两个正整数，则存在正整数 a' ,b' ，满足 a'| a,b'| b,(a' ,b') =1,a' b' = [a,b] §1.4 习题 1. 设 p 是正整数 n 的最小素因数，证明：若 1/ 3 p n ， 则 n/ p 是素数。 2. 设 n 1 。证明： ( 1) | ( 1) 2 − − k n n 的充要条件是 (n −1)| k。 3. 证明对于一切整数，n 2+2n+12 都不是121 的倍数。 4. 证明：（1） 24 | n(n +1)(n + 2)(n + 3) ；（2） n − n 5 30 | 。 5. 证明对于任意整数 n ， n n n 15 7 3 1 5 1 5 3 + + 是整数。 6. 证明：当 n 为大于 1 的正整数时， n s 1 3 1 2 1 1 =1+ + ++
不是整数。 7设p为大于1的正整数,若对任意的整数a,b,由 p|ab可推出p|a或p|b至少有一个成立,则p 定是素数 8.设n>2,证明在n和n!之间一定有一个素数。 9.设a是奇数。证明:必有正整数d使得 (24-3,a) 10^用C语言实现算法1.2.6,并求不定方程 7x+4y=0在|x|≤1000.且|y1000下的一切整 数解。 11如果一个正整数具有20个正因数,问这个正整 数最小是什么? 12求满足d(m)=6的最小正整数,并且证明n的全部 正因数的乘积等于nm2
不是整数。 7. 设 p 为大于 1 的正整数，若对任意的整数 a,b ，由 p | ab 可推出 p | a 或 p | b 至少有一个成立，则 p一 定是素数。 8. 设 n>2，证明在 n 和 n!之间一定有一个素数。 9. 设 a 是 奇 数 。 证 明 ： 必 有 正 整 数 d 使 得 (2 − 3,a) =1 d 。 10. 用 C 语 言实现 算法 1.2.6 ，并 求不 定方程 7x + 4y = 0 在 | x |1000,且| y |1000 下的一切整 数解。 11. 如果一个正整数具有 20 个正因数，问这个正整 数最小是什么？ 12. 求满足 d(n) = 6 的最小正整数，并且证明 n 的全部 正因数的乘积等于 d ( n ) / 2 n