《初等数论 第一章 整除精.ppt》由会员分享，可在线阅读，更多相关《初等数论 第一章 整除精.ppt（58页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、初等数论初等数论 第一章第一章 整整除除 2022/10/5 *第1页，本讲稿共58页 2022/10/5 *数论的基本内容数论的基本内容按照研究方法的不同，数论可分为按照研究方法的不同，数论可分为初等数论初等数论解析数论解析数论代数数论代数数论几何数论几何数论第2页，本讲稿共58页 2022/10/5 *参考书目参考书目1、南基洙主编初等数论；、南基洙主编初等数论；2、柯召、孙琦编著数论讲义，高等教育、柯召、孙琦编著数论讲义，高等教育出版社；出版社；3、闵嗣鹤、严士健编初等数论，高等教、闵嗣鹤、严士健编初等数论，高等教育出版社；育出版社；4、郑克明主编初等数论，西南师范大学郑克明主编初等数论
2、，西南师范大学出版社。出版社。第3页，本讲稿共58页 2022/10/5 *初等数论初等数论第一章第一章 整除整除 1 自然数与整数自然数与整数 第4页，本讲稿共58页 2022/10/5 *归纳原理归纳原理归纳原理归纳原理设设S是是N的一个子集，满足条件：的一个子集，满足条件：()1S;()如果如果n S，则，则n+1 S,那么，那么，S=N.第5页，本讲稿共58页 2022/10/5 *定理定理定理定理1 1 数学归纳法数学归纳法数学归纳法数学归纳法 设设P(n)是关于自然数是关于自然数n的一种性质或命题的一种性质或命题.如果如果 ()当当n=1时，时，P(1)成立；成立；()由由P(n)
3、成立必可推出成立必可推出P(n+1)成立，成立，那么，那么，P(n)对所有自然数对所有自然数n成立成立.第6页，本讲稿共58页 2022/10/5 *定理定理2 最小自然数原理最小自然数原理设设T是是N的一个非空子集的一个非空子集.那么，必有那么，必有t0 T,使对任意的使对任意的t T有有t0t，即，即t0是是T中的最小中的最小自然数自然数.第7页，本讲稿共58页 2022/10/5 *定理定理定理定理3 3 最大自然数原理最大自然数原理最大自然数原理最大自然数原理 设设M是是N的非空子集的非空子集.若若M有上界，即存在有上界，即存在 aN,使对任意的使对任意的m M有有m a,那么必那么必
4、 有有m0 M，使对任意的，使对任意的m M有有m m0，即即m0是是M中的最大自然数。中的最大自然数。第8页，本讲稿共58页 2022/10/5 *定理定理4 第二数学归纳法第二数学归纳法设设 P(n)是关于自然数是关于自然数 n 的一种性质或命题的一种性质或命题.如果如果()当当 n=1 时，时，P(1)成立；成立；()设设 n1.若对所有的自然数若对所有的自然数 mn,P(m)成立，成立，则必可推出则必可推出P(n)成立，那么成立，那么,P(n)对所有对所有自然数自然数 n 成立成立.第9页，本讲稿共58页 2022/10/5 *定理定理5 鸽巢原理鸽巢原理设设n是一个自然数是一个自然数
5、.现有现有n个盒子和个盒子和n+1个物体个物体.无论怎样把这无论怎样把这n+1个物体放入这个物体放入这n个盒子中，个盒子中，一定有一个盒子中被放了两个或两个以上的一定有一个盒子中被放了两个或两个以上的物体。物体。第10页，本讲稿共58页 2022/10/5 *2 整除整除第11页，本讲稿共58页 2022/10/5 *定义定义1设设a，b是整数，是整数，a 0，如果存在整数，如果存在整数q，使得使得b=aq，则称，则称b可被可被a整除，记作整除，记作a b，且称且称b是是a的倍数，的倍数，a是是b的约数的约数(因数、除数因数、除数)；如果不存在整数如果不存在整数q使得使得b=aq成立，则称成立
6、，则称b不被不被a整除，记为整除，记为a b。被被2整除的数称为偶数，不被整除的数称为偶数，不被2整除的称为奇数整除的称为奇数 第12页，本讲稿共58页 2022/10/5 *定理定理1 下面的结论成立：下面的结论成立：()a|b (-a)|b a|(-b)(-a)|(-b)|a|b|；()a b，b c a c；()a b,a c 对任意对任意 x、y,有有a bx+cy,一般地，一般地，a bi，i=1,2,k a b1x1 b2x2 bkxk，此处此处xi（i=1,2,k）是任意的整数；）是任意的整数；()a b ac bc，c是任意的非零整数；是任意的非零整数；()a b且且b a a
7、=b；()a b，b 0|a|b|；a b且且|b|1是合数的充要条件是是合数的充要条件是 a=de,1da,1e1,q是不可约数且是不可约数且d|q,则则d=q.定理定理4 若若a是合数，则必有不可约数是合数，则必有不可约数p|a.第17页，本讲稿共58页 2022/10/5 *定理5 设整数设整数设整数设整数a a2,2,那么那么那么那么a a一定可表为素数的乘积一定可表为素数的乘积一定可表为素数的乘积一定可表为素数的乘积(包括包括a本身是素数本身是素数)，即，即 a=p1p2 ps其中其中pj（1j s)是素数是素数.证明证明 当当a=2时，结论显然成立。时，结论显然成立。假设对于假设对
8、于2 a k，式，式(1)成立，我们来证明式成立，我们来证明式(1)对于对于a=k 1也成立，若也成立，若k 1是素数，式是素数，式(1)显成立显成立.如果如果k 1是合数，则存在素数是合数，则存在素数p与整数与整数d，使得，使得k 1=pd.由于由于2 d k，由归纳假定知存在素数，由归纳假定知存在素数q1,q2,ql，使得，使得d=q1q2ql，从而，从而k 1=pq1q2ql.从而由归纳法推出式从而由归纳法推出式(1)对任何大于对任何大于1的整数的整数a成立。成立。证毕。证毕。第18页，本讲稿共58页 2022/10/5 *推论推论任何大于任何大于1的合数的合数a必有一个不超过必有一个不
9、超过a1/2的素的素因数。因数。证明证明 由于由于 a是合数，故存在整数是合数，故存在整数 b和和 c使使 abc,其中其中:1ba,1ca.若若b和和c均大于均大于a1/2 ,则则abca1/2a1/2a,这是不可能的这是不可能的.因此因此b和和c中必有一个小于或等于中必有一个小于或等于a1/2.第19页，本讲稿共58页 2022/10/5 *例例5 写出不超过写出不超过100的所有的素数的所有的素数.解解 将不超过将不超过100的正整数排列如下：的正整数排列如下：1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25
10、26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 5051 52 53 54 55 56 57 58 59 6061 62 63 64 65 66 67 68 69 7071 72 73 74 75 76 77 78 79 8081 82 83 84 85 86 87 88 89 9091 92 93 94 95 96 97 98 99 100第20页，本讲稿共58页 2022/10/5 *按以下步骤进行：按以下步骤进行：()删去删去1，剩下的后面的第一个数是，剩下的后面的第一个数是2，2是素数；是素数；
11、()删去删去2后面的被后面的被2整除的数，剩下的整除的数，剩下的2后面的第后面的第一个数是一个数是3，3是素数；是素数；()再删去再删去3后面的被后面的被3整除的数，剩下的整除的数，剩下的3后面的后面的第一个数是第一个数是5，5是素数；是素数；()再删去再删去5后面的被后面的被5整除的数，剩下的整除的数，剩下的5后面的后面的第一个数是第一个数是7，7是素数；是素数；照以上步骤可以依次得到素数照以上步骤可以依次得到素数2,3,5,7,11,.由定理由定理2推论可知，不超过推论可知，不超过100的合数必有一个不超的合数必有一个不超过过10的素约数，因此在删去的素约数，因此在删去7后面被后面被7整除
12、的数以后，整除的数以后，就得到了不超过就得到了不超过100的全部素数的全部素数.第21页，本讲稿共58页 2022/10/5 *在例在例5中所使用的寻找素数的方法中所使用的寻找素数的方法,称为称为Eratosthenes筛法筛法.它可以用来求出不超它可以用来求出不超过任何固定整数的所有素数过任何固定整数的所有素数.在理论上这在理论上这是可行的；但在实际应用中，这种列出是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不素数的方法需要大量的计算时间，是不可取的可取的.第22页，本讲稿共58页 2022/10/5 *定理定理7.(Euclid)素数有无穷多个素数有无穷多个.证明：证
13、明：(反证法反证法)假设素数是有限多个假设素数是有限多个,共有共有n个个,令它们是令它们是p1,p2,pn,并令并令a=p1p2pn+1.若若a是素数是素数,则因则因api，其中，其中1i 1，那么由，那么由d ai（1 i k）推出）推出d a1x1 a2x2 akxk=1，这是不可能的，这是不可能的.所以有所以有(a1,a2,ak)=1.证毕证毕.第29页，本讲稿共58页 2022/10/5 *定理定理 10设正整数设正整数m|(a1,a2,ak).我们有我们有m(a1/m,a2/m,ak/m)=(a1,a2,ak)特别地有特别地有 =1.第30页，本讲稿共58页 2022/10/5 *定
14、义定义 6 最小公倍数最小公倍数设设a1,a2,ak和和m都是整数都是整数,k2.若若ai|m,1ik,则称则称m是是a1,a2,ak的公倍数的公倍数.在在a1,a2,ak所有公倍数中最小的那一个所有公倍数中最小的那一个正整数正整数,称为称为a1,a2,ak的最小公倍数的最小公倍数,记为记为 a1,a2,ak.第31页，本讲稿共58页 2022/10/5 *定理定理 11()a1,a2=a2,a1=-a1,a2.一般地有一般地有,a1,a2,ai,ak=ai,a2,a1,ak=-a1,a2,ai,ak()若若a2|a1,则则a1,a2=|a1|；()对任意的对任意的d|a1a1,a2=a1,a
15、2,da1,a2,ak=a1,a2,ak,d第32页，本讲稿共58页 2022/10/5 *定理定理12设设m0,我们有我们有ma1,mak=ma1,ak第33页，本讲稿共58页 2022/10/5 *3 带余除法与辗转相除法带余除法与辗转相除法第34页，本讲稿共58页 2022/10/5 *定理定理1 带余数除法带余数除法设设a与与b是两个整数，是两个整数，a 0,则存在唯一的两个整数则存在唯一的两个整数q和和r，使得，使得 b=aq r，0 r|a|(1)证明证明 存在性存在性 若若a b，b=aq，q Z，可取，可取r=0.若若a b，考虑集合，考虑集合 A=b ka；k Z，在集合在集
16、合A中有无限多个正整数，设最小的正整数是中有无限多个正整数，设最小的正整数是r=b k0a，则必有，则必有 0 r|a|，即即 b k0a|a|，b k0a|a|0，这样，这样,在集合在集合A中中,又有正整数又有正整数r1=b k0a|a|r，这与，这与r的最小性矛盾。的最小性矛盾。第35页，本讲稿共58页 2022/10/5 *所以式所以式(2)必定成立必定成立.取取q=k0 知式知式(1)成立成立.存在性得证存在性得证.唯一性唯一性 假设有两对整数假设有两对整数q 、r 与与q 、r 都使都使得式得式(1)成立，即成立，即b=q a r =q a r ，0 r ,r|a|，则，则(q q
17、)a=r r ，|r r|0.任一整数被任一整数被 a 除后所得的最小非负余除后所得的最小非负余数是且仅是数是且仅是0,1,a-1这这a个数中的一个个数中的一个.由此由此全体整数按被全体整数按被a除后所得的最小非负余数除后所得的最小非负余数可分为两两不相交的可分为两两不相交的a个类个类.0moda,1moda,(a-1)modaa=2时，全体整数分为两类：时，全体整数分为两类：0mod2，1mod2第39页，本讲稿共58页 2022/10/5 *例例2()0mod2 0mod3=0mod6;()1mod2 1mod3=1mod6；()0mod2 1mod3=4mod6.例例31mod2=1mo
18、d63mod65mod6第40页，本讲稿共58页 2022/10/5 *例例4 a a进位表示进位表示 设设a 2是给定的正整数是给定的正整数.那么，任一正整数那么，任一正整数n必可唯一表为必可唯一表为 n=rkak+rk-1ak-1+r1a+r0,(4)其中整数其中整数k 0，0 rj a-1，(0 j k)，rk0.这就是正整数的这就是正整数的a进位进位表示表示.第41页，本讲稿共58页 2022/10/5 *例例5 设设a2是奇数是奇数.证明：证明：()一定存在正整数一定存在正整数d a-1,使得使得a|2d-1.()设设d0是满足是满足()的最小正整数的最小正整数d.那么，那么，a|2
19、h-1(hN)的充要条件是的充要条件是 d0|h.()必有正整数必有正整数d使得（使得（2d-3,a)=1.第42页，本讲稿共58页 2022/10/5 *定理定理4 (Euclid)欧几里德算法欧几里德算法.设设 a,b是给定的两个整数，是给定的两个整数，b0,b a.我们一定我们一定可以重复定理可以重复定理1得到下面的等式：得到下面的等式：a=bq1+r1,0rl|b|b=r1q2+r2,0r2r1 r1=r2q3+r3,0r3r2 .rn-2=rn-1qn+rn,0rnrn-1 rn-1=rnqn+1+0则则(a,b)=rn.第43页，本讲稿共58页 2022/10/5 *证明证明:由于
20、由于|b|r1r2rn0,故欧几里故欧几里德算法中的带余除法必在有限步内得到一个德算法中的带余除法必在有限步内得到一个余数是零的等式余数是零的等式,即即rn+1=0.根据前面定理可知：根据前面定理可知：(a,b)=(b,r1)=(rn-1,rn)=(rn,0)=rn.欧几里德算法也称辗转相除法欧几里德算法也称辗转相除法.第44页，本讲稿共58页 2022/10/5 *在在Euclid算法中算法中,由由:rn=rn-2-rn-1qn,rn-1=rn-3-rn-2qn-1,得得 rn=rn-2(1+qnqn-1)-rn-3qn,再将再将rn-2=rn-4-rn-3qn-2代入代入上式上式,如此继续
21、下去如此继续下去,最后得到最后得到:rn=sa+tb,其中其中 s和和t是整数是整数.于是有于是有(a,b)是是 a和和b线性组合表示定理线性组合表示定理.定理定理5()若任给整数若任给整数 a,b,则存在整数则存在整数x和和 y,使得使得 (a,b)=ax+by.容易证明下面结论容易证明下面结论()a和和b的公因数整除的公因数整除(a,b).第45页，本讲稿共58页 2022/10/5 *例例6用欧几里德算法求用欧几里德算法求(1997,57).用用1997和和57的线性组合表示的线性组合表示(1997,57)求求1997和和57的所有公因数的所有公因数解解 用下划线标识余数用下划线标识余数
22、 19975735+2 57228+1 2l2+0因此因此,(1997,57)=l,即即1997和和57是互素的是互素的.第46页，本讲稿共58页 2022/10/5 *1=57-228 =57-(1997-5735)28 =-281997+(57+573528）=-281997+98157由于由于1997和和57是互素的是互素的,公因数只有公因数只有1和和-1.第47页，本讲稿共58页 2022/10/5 *例例7设设m,n是正整数是正整数.证明证明（2m-1,2n-1)=2(m,n)-1第48页，本讲稿共58页 2022/10/5 *4 最大公因数理论最大公因数理论第49页，本讲稿共58页
23、 2022/10/5 *定理定理定理定理1 1 aj|c(1(1j j k k)的充要条件是的充要条件是的充要条件是的充要条件是 a1,ak|c证明：充分性显然证明：充分性显然.必要性，设必要性，设a1,ak=m.c是是a1,ak的的任任一公倍数一公倍数,利用带余除法得利用带余除法得:c=mq+r,0rm,aj|c,aj|m,aj|r,(1j k).故故a1|r,ak|r,即即r是是a1,ak的公倍数的公倍数.但由于但由于:1rm与与 m是是 a1,ak的最小公倍数发生矛盾的最小公倍数发生矛盾,故故:r=0,即即:c mq.故故m|c.即即a1,ak|c第50页，本讲稿共58页 2022/10
24、/5 *定理定理2设设D是正整数是正整数.那么那么D=（a1,a2,ak）的充）的充要要条件是：条件是：()D|aj(1 j k);()若若d aj(1 j k),则则d(a1,a2,ak).这个结论表明：公约数一定是最大公约数的这个结论表明：公约数一定是最大公约数的约数。约数。第51页，本讲稿共58页 2022/10/5 *定理定理3(ma1,ma2,mak)=|m|(a1,a2,ak).定理定理 4 ()(a1,a2,ak)=(a1,a2),a3,ak)；()(a1,a2,ak+r)=(a1,ak),(ak+1,ak+r)；推论推论（a1,a2)(b1,b2)=(a1b1,a1b2,a2b
25、1,a2b2)第52页，本讲稿共58页 2022/10/5 *定理定理5若若(m,a)=1，则，则(m,ab)=(m,b).证明证明:(m,b)=(m,(m,a)b)=(m,mb,ab)=(m,ab).推论推论 若若(a,bi)=1,1 i n,则则 (a,b1b2bn)=1.第53页，本讲稿共58页 2022/10/5 *定理定理6对于任意的整数对于任意的整数a，b，m，下面的结论成立：，下面的结论成立：()由由m ab及及(m,a)=1可以推出可以推出m b；()由由m1 n，m2 n及及(m1,m2)=1可以推出可以推出m1m2 n.一般地，若一般地，若m1,m2,mk两两互素，及两两互
26、素，及mj n(1 j k），则），则m1 m2 mk n.证明：证明：()(m,a)=1，则，则(m,ab)=(m,b)，由，由m ab，(m,ab)=|m|，故，故(m,b)=|m|，从而，从而m b.()m1 n知知n=m1n1,m2 n,即即m2 m1n1,又又(m1,m2)=1,知知m2 n1，因而因而m1m2 n.第54页，本讲稿共58页 2022/10/5 *定理定理7设设a1和和a2是正整数是正整数,且且(a1,a2)=d,a1,a2=m,则则a1a2md.第55页，本讲稿共58页 2022/10/5 *例例例例1 1设设p是素数是素数.证明：证明：()p|，1 j p-1()
27、对任意的正整数对任意的正整数a,p|ap-a;()若若(p,a)=1，则，则p|ap-1-1.例例2 证明：证明：()(a,uv)=(a,(a,u)v);()(a,uv)|(a,u)(a,v)第56页，本讲稿共58页 2022/10/5 *例例3设设k是正整数是正整数.若一个有理数的若一个有理数的k次方是整数，次方是整数，那么，这个有理数一定是整数那么，这个有理数一定是整数.第57页，本讲稿共58页 2022/10/5 *例例例例4 4设设k是正整数是正整数.证明：证明：()(ak,bk）=(a,b)k;()设设a,b是正整数是正整数.若若(a,b)=1,ab=ck,则则a=(a,c)k,b=(b,c)k例例5 设设m2,(m,a)=1,证明：证明：()存在正整数存在正整数d m-1,使得使得m ad-1;()设设d0是满足是满足()的最小正整数的最小正整数d，那么，那么，m ah-1(h1)的充要条件是的充要条件是d0|h.第58页，本讲稿共58页