初等數(shù)論第一章整除

1、初等數(shù)論第一章整除 2022/9/3 *第1頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *定理1設(shè)a1,a2,an都是正整數(shù),且p是素?cái)?shù). 若p|a1a2an,則至少有一個(gè)ar, 使得p|ar, 其中1rn.證明 假設(shè) ai不能被p整除, 1in. 從p是一素?cái)?shù)和定理得到(p,a1)=(p,a2)=(p,an)=1. 所以由定理5推論得到(p,a1a2an)=1, 這與題設(shè)p|a1a2an矛盾, 故必有一ar, 使得p|ar, 其中1rn.第2頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *推論設(shè)p1,p2,pn和p都是素?cái)?shù),

2、n2. 若p|p1p2pn, 則至少有一個(gè)pr, 使得p=pr.證明 由p| p1p2pn和定理1知, 至少存在一個(gè)pr, 使得p|pr. 由于pr是素?cái)?shù), 故它只有二個(gè)正因數(shù)1和pr. 由p1和p| pr, 所以: p= pr.第3頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *定理2 (整數(shù)分解唯一性定理)每個(gè)大于1的正整數(shù)a均可分解成有限個(gè)素?cái)?shù)之積, 并且若不計(jì)素因數(shù)的次序, 其分解是唯一的.證明 先證分解式的存在性. 唯一性. 當(dāng)a=2時(shí), 分解式顯然是唯一的. 現(xiàn)設(shè)比a小的正整數(shù)其分解式均是唯一的. 考慮正整數(shù) a, 假設(shè) a有兩個(gè)分解式 a=plp2

3、pk和a=q1q2ql, 其中pl,p2,pk和q1,q2,ql都是素?cái)?shù).第4頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *于是p1| q1q2ql , 根據(jù)定理1知必有一qi, , 使得p1|qi，不妨令i=1, 即p1|q1, 顯然p1=q1. 令a=a/p1,則a=p2p3pk, aq2q2ql. 若a=1, 則a= p1=q1,即a的分解式唯一. 若a1, 注意到aa, 從而由歸納假設(shè)知, a的分解式是唯一的. 因此k=l,并且 p1=q1,pk=qk, 再由p1=ql, 知a分解式也是唯一的.第5頁，共23頁，2022年，5月20日，13點(diǎn)35分，星

4、期一 2022/9/3 *若將a的分解式中相同素因數(shù)合并為它的冪數(shù), 則任意大于1的整數(shù)a只能分解成一種形式: (2)p1 p2 psn1, 其中p1,p2,ps是互不相同的素?cái)?shù), , , 是正整數(shù). 并稱其是 a的標(biāo)準(zhǔn)分解式.第6頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *推論3使用式(2)中的記號(hào)，有() d 是a的正因數(shù)的充要條件是 d = (3) eiZ，0 ei i，1 i s；() n的正倍數(shù)m必有形式m = M，MN，iN，i i，1 i s。第7頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *推論 設(shè)正整數(shù)a與

5、b的標(biāo)準(zhǔn)分解式是 其中pi (1 i k)，qi (1 i l)與ri (1 i s)是兩兩不相同的素?cái)?shù), i , i (1 i k), i(1 i l)與i（1 i s）都是非負(fù)整數(shù)，則(a, b) = ， i = mini, i, 1 i k，a, b = ， i = maxi, i，1 i k。第8頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *推論4設(shè)正整數(shù)a與b的分解式是其中p1, p2, , ps 是互不相同的素?cái)?shù)，i，i（1 i k）都是非負(fù)整數(shù)，則第9頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *推論5設(shè)a，b，

6、c，k是正整數(shù)，ab = ck ，(a, b) = 1，則存在正整數(shù)u，v，使得a = uk，b = vk，c = uv，(u, v) = 1。證明 設(shè) ，其中p1, p2, , ps 是互不相同的素?cái)?shù)， i （1 i s）是正整數(shù)。又設(shè) 其中i ，i（1 i s）都是非負(fù)整數(shù)。顯然mini , i = 0， i i = k i ，1 i s，因此，對(duì)于每個(gè)i（1 i s），等式i = ki ，i = 0與i = 0，i = ki有且只有一個(gè)成立。這就證明了推論。證畢。第10頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *推論6設(shè)a是正整數(shù)， 表示a的所有正因數(shù)

7、的個(gè)數(shù).若a有標(biāo)準(zhǔn)素因數(shù)分解式(2)，則推論7 設(shè)a是正整數(shù)， 表示a的所有正因數(shù)的之和.若a有標(biāo)準(zhǔn)素因數(shù)分解式(2)，則第11頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *例1 證明：（a,b,c)=(a,b),(a,c)例2 求 ，例3 求第12頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *7 函數(shù)x與x , n!的分解式第13頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *定義1設(shè)x是實(shí)數(shù)，以x表示不超過x的最大整數(shù)，稱它為x的整數(shù)部分，即x是一個(gè)整數(shù)且滿足 x x x+1.又稱x = x

8、 x為x的小數(shù)部分。 第14頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *定理1 設(shè)x與y是實(shí)數(shù)，則() x y x y；() 若x=m+v, m是整數(shù)， 0 v 1, 則m= x, v=x，特別地，若0 x 1，則x = 0，x =x ；() 若m是整數(shù)，則m x = m x；() x y = ；() x = ；第15頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *x = .()對(duì)正整數(shù)m有()設(shè)a和N是正整數(shù).那么，正整數(shù)中被a整除的正整數(shù)的個(gè)數(shù)是第16頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9

9、/3 *證明能被a整除的正整數(shù)是a, 2a, 3a, ，因此，若數(shù)1, 2, , N中能被a整除的整數(shù)有k個(gè)，則ka N (k 1)a k N/a k 1 k = 證畢。由以上結(jié)論我們看到，若b是正整數(shù)，那么對(duì)于任意的整數(shù)a，有即在帶余數(shù)除法 a = bq r，0 r 0(1 j s),并且n=a1+a2+as.證明：n!/a1!a2! as!是整數(shù).第21頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一 2022/9/3 *例5設(shè)n是正整數(shù)，1 k n 1，則 N (3)若n是素?cái)?shù)，則n ，1 k n 1.證明 由定理2，對(duì)于任意的素?cái)?shù)p，整數(shù)n!，k!與(n k)!的標(biāo)準(zhǔn)分解式中所含的p的指數(shù)分別是利用例4可知第22頁，共23頁，2022年，5月20日，13點(diǎn)35分，星期一