《整除帶余除法輾轉(zhuǎn)》PPT課件.ppt

1、,專業(yè)基礎(chǔ)課程 初等數(shù)論 Number Theory 邯鄲學(xué)院數(shù)學(xué)系 石立葉,前言,初等數(shù)論,前言,主要 內(nèi)容,第一章 整數(shù)的整除性,1.整除概念和帶余除法,2.最大公因數(shù)和輾轉(zhuǎn)相除法,3.質(zhì)數(shù)的性質(zhì)及最小公倍數(shù),4.質(zhì)數(shù).算數(shù)基本定理,第一節(jié) 整除的概念 帶余除法,定義 設(shè)a,b是任意兩個(gè)整數(shù)，其中 如果存在一個(gè)整數(shù)q，使得 (1)成立， 我們就說(shuō)b整除a,或a能被b整除，記 作： ，b叫做因數(shù)，a叫做倍數(shù)。 若這樣的q不存在，則稱b不能整除a,或a 不能被b整除，記做b a,整除概念,整除性質(zhì),帶余除法,定理1 若 ，則 證 ： 定理2： 若 定理3： 若,第一節(jié) 整除的概念 帶余除法,整

2、除概念,整除性質(zhì),帶余除法,例 若n是奇數(shù)，則8n2 1。 解 設(shè)n = 2k 1，則 n2 1= (2k 1)2 1 = 4k(k 1)，在k和k 1 中有一個(gè)是偶數(shù)，所以8 n2 1 例 以d(n)表示n的正約數(shù)的個(gè)數(shù)，例如： d(1) = 1，d(2) = 2，d(3) = 2，d(4) = 3， 問(wèn)：d(1) d(2) d(1997)是否為偶數(shù)？ 提示：442 1997 452,第一節(jié) 整除的概念 帶余除法,帶余除法： 若a和b是兩個(gè)整數(shù)，其中b0,則存在兩個(gè) 整數(shù)q及r,使得 （2） 成立，而且q及r 是唯一的 q叫做a被b整除所得的不完全商，r叫做a被 b整除所得的余數(shù),第一節(jié) 整

3、除的概念 帶余除法,整除概念,整除性質(zhì),帶余除法,注：帶余除法要注意兩點(diǎn):b0 例：a=255,b=15,求商和余數(shù) a=417,b=15,求商和余數(shù) a=-81,b=15,求商和余數(shù) 例：a是兩位數(shù)，a除310的余數(shù)為37，則a=? 例：證明 ，其中n是任何整數(shù),第一節(jié) 整除的概念 帶余除法,第一節(jié) 整除的概念 帶余除法,回顧：,倍數(shù)和因數(shù),性質(zhì),帶余除法,第二節(jié) 最大公因數(shù)與輾轉(zhuǎn)相除法,定義 設(shè) 是 個(gè)整 數(shù)，若d是它們之中每一個(gè)的因數(shù)，那末d就 叫做 的一個(gè)公因數(shù) 最大公因數(shù) 整數(shù) 的公因數(shù)中 最大的一個(gè)，記作： 若 =1，我們說(shuō) 互素，或互質(zhì) 若每?jī)蓚€(gè)整數(shù)互質(zhì)，兩兩互質(zhì),定理1：若 是

4、任意n個(gè)不全為 零的整數(shù)，則 (1) 與 的公因數(shù) 相同 (2) 例:(6,-4)=(6,4) 所以，我們只要討論非負(fù)整數(shù)的公 因數(shù)，,第二節(jié) 最大公因數(shù)與輾轉(zhuǎn)相除法,設(shè)a,b是非負(fù)整數(shù)，分情況： (1)兩個(gè)都為零 最大公因數(shù)不存在 (2)有一個(gè)為零 設(shè)a=0,（a,b）=(0,b)=b (3)兩個(gè)都不為零 即 定理3 設(shè)a,b,c是任意三個(gè)不全為零的整數(shù)，且 a=bq+c,q是不等于零的整數(shù)，則a,b和b,c的公因 數(shù)相同，因而(a,b）=(c,b) 兩個(gè)都不為零 (1) (2)a不整除b，或b不整除a,第二節(jié) 最大公因數(shù)與輾轉(zhuǎn)相除法,定理4 若a和b是任意兩個(gè)整數(shù)，則(a,b) 等于(2)

5、式中倒數(shù)第一個(gè)不為零的余數(shù)，即 （2）式所提供求最大公因數(shù)的方法叫做輾轉(zhuǎn)相除法，也稱歐幾里德算法 例 求(1859,1573) 例 求(169,121) 例 用歐幾里德算法求(1997,57). 用1997和57的線性組合表示(1997,57) 求1997和57的所有公因數(shù),第二節(jié) 最大公因數(shù)與輾轉(zhuǎn)相除法,定理5 設(shè)a,b是任意兩個(gè)不全為零的整數(shù)， (1) 若m是任意正整數(shù)，則（am,bm）=(a,b)m (2) 若 是a,b任一公因數(shù)，則 特別的 定理6 若 是任意n個(gè)不全為零的整數(shù)，則,第二節(jié) 最大公因數(shù)與輾轉(zhuǎn)相除法,練習(xí)：判斷： 1、任意非零整數(shù)b,（0,b）=b 2、設(shè)m是任意非零整數(shù)

6、，則 （am,bm）=(a,b)m 3、設(shè)-2是a,b的公因數(shù)，則 4、如果a,b是兩個(gè)整數(shù), ,則存在唯一的整數(shù)對(duì) ,使得 ,其中,第二節(jié) 最大公因數(shù)與輾轉(zhuǎn)相除法,輾轉(zhuǎn)相除法和帶余除法的關(guān)系,第三節(jié) 整除的進(jìn)一步性質(zhì)及最小公倍數(shù),定理1 若a,b是任意兩個(gè)整數(shù)，則 其中,推論1.1：若a,b是任意兩個(gè)不全為零的整 數(shù)，則存在兩個(gè)整數(shù)s,t 使得as+bt=(a,b) 定理2：若a,b,c是三個(gè)不全為零的整數(shù)， 且（a,c）=1，則 (1) ab,c與b,c有相同的公因數(shù) (2) (ab,c)=(b,c) 推論2.1：若(a,c)=1，c|ab,則c|b 證明：|c|=(c,ab)=(c,b)

7、 所以，c|b,第三節(jié) 整除的進(jìn)一步性質(zhì)及最小公倍數(shù),例：(-120,28)=(120,28)=(120,4)=4 例:(390,91)=(39,91)=(17,91)=17,推論2.2：設(shè) 及 是 任意兩組整數(shù)，若前一組中任一整數(shù)與后一組 中任一整數(shù)互質(zhì)，則 與 互質(zhì) 證明：由定理2，知,第三節(jié) 整除的進(jìn)一步性質(zhì)及最小公倍數(shù),定義 設(shè) 是 個(gè)整數(shù)，若d是這n個(gè)數(shù)的倍數(shù)，則d就叫做這n個(gè)數(shù)的公倍數(shù)。 又在 的一切公倍數(shù)中的最小正整數(shù)叫做最小公倍數(shù)，記作 注：因?yàn)槿魏握龜?shù)都不是0的倍數(shù)，所以，在討論最小公倍數(shù)時(shí)，假定這些整數(shù)不為0,第三節(jié) 整除的進(jìn)一步性質(zhì)及最小公倍數(shù),定理3 定理4 設(shè)a,b是任意兩個(gè)正整數(shù)，則 (1) a,b的最小公倍數(shù)就是a,b的所有倍數(shù) a,b= 設(shè) 是n個(gè)正整數(shù)，令 定理5 若 是n個(gè)正整數(shù)，則,定理4和定理5給出了最小公倍數(shù)的求法 最小公倍數(shù)和最大公約數(shù)都是正數(shù),第三節(jié) 整除的進(jìn)一步性質(zhì)及最小公倍數(shù),練習(xí)： 1 求24871與3468的最大公因數(shù)，最小公倍數(shù) ? 2 求136,221,391