初等数论第一章整除.ppt

《初等数论第一章整除.ppt》由会员分享，可在线阅读，更多相关《初等数论第一章整除.ppt（58页珍藏版）》请在三一办公上搜索。

1、2023/9/5 22:14,初等数论 教师：何艳,2023/9/5 22:14,数论的基本内容,按照研究方法的不同，数论可分为初等数论解析数论代数数论几何数论,2023/9/5 22:14,参考书目,1、南基洙主编初等数论；2、柯召、孙琦编著数论讲义，高等教育出版社；3、闵嗣鹤、严士健编初等数论，高等教育出版社；4、郑克明主编初等数论，西南师范大学出版社。,2023/9/5 22:14,初等数论,第一章 整除 1 自然数与整数,2023/9/5 22:14,归纳原理,设S是N的一个子集，满足条件：()1S;()如果n S，则n+1 S,那么，S=N.,2023/9/5 22:14,定理1 数

2、学归纳法,设P(n)是关于自然数n的一种性质或命题.如果()当n=1时，P(1)成立；()由P(n)成立必可推出P(n+1)成立，那么，P(n)对所有自然数n成立.,2023/9/5 22:14,定理2 最小自然数原理,设T是N的一个非空子集.那么，必有t0 T,使对任意的t T有t0t，即t0是T中的最小自然数.,2023/9/5 22:14,定理3 最大自然数原理,设M是N的非空子集.若M有上界，即存在 aN,使对任意的m M有m a,那么必 有m0 M，使对任意的m M有m m0，即m0是M中的最大自然数。,2023/9/5 22:14,定理4 第二数学归纳法,设 P(n)是关于自然数

3、n 的一种性质或命题.如果()当 n=1 时，P(1)成立；()设 n1.若对所有的自然数 mn,P(m)成立，则必可推出P(n)成立，那么,P(n)对所有自然数 n 成立.,2023/9/5 22:14,定理5 鸽巢原理,设n是一个自然数.现有n个盒子和n+1个物体.无论怎样把这n+1个物体放入这n个盒子中，一定有一个盒子中被放了两个或两个以上的物体。,2023/9/5 22:14,2 整除,2023/9/5 22:14,定义1,设a，b是整数，a 0，如果存在整数q，使得b=aq，则称b可被a整除，记作ab，且称b是a的倍数，a是b的约数(因数、除数)；如果不存在整数q使得b=aq成立，则

4、称b不被a整除，记为a b。被2整除的数称为偶数，不被2整除的称为奇数,2023/9/5 22:14,定理1 下面的结论成立：,()a|b(-a)|b a|(-b)(-a)|(-b)|a|b|；()ab，bc ac；()ab,ac 对任意 x、y,有abx+cy,一般地，abi，i=1,2,k ab1x1 b2x2 bkxk，此处xi（i=1,2,k）是任意的整数；()ab acbc，c是任意的非零整数；()ab且ba a=b；()ab，b 0|a|b|；ab且|b|a|b=0.,2023/9/5 22:14,例1 证明：若3|n且7|n，则21|n.例2 设a=2t-1.若a|2n,则a|n

5、.例3 设a、b是两个给定的非零整数，且有整数x、y，使得 ax+by=1.证明：若a|n且b|n,则ab|n.例4 设f(x)=anxn+an-1xn-1+a1x+a0 Zx,其中Zx表示全体一元整系数多项式组成的集合.若d|b-c,则 d|f(b)-f(c).,2023/9/5 22:14,定义2,显然每个非零整数a都有约数 1，a，称这四个数为a的显然因数，a的另外的因数称为非显然因数。若整数a 0，1，并且只有约数 1和 a，则称a是素数（或质数）；否则称a为合数。以后在本书中若无特别说明，素数总是指正素数。,2023/9/5 22:14,定理2,设A=d1,d2,dk 是n的所有约数

6、的集合，则B=也是n的所有约数的集合。解 由以下三点理由可以证得结论：()A和B的元素个数相同；()若diA，即din，则 n，反之亦然；()若di dj，则.,2023/9/5 22:14,定理3,()a1是合数的充要条件是 a=de,11,q是不可约数且d|q,则d=q.定理4 若a是合数，则必有不可约数p|a.,2023/9/5 22:14,定理5 设整数a2,那么a一定可表为素数的乘积,(包括a本身是素数)，即 a=p1p2 ps其中pj（1j s)是素数.证明 当a=2时，结论显然成立。假设对于2 a k，式(1)成立，我们来证明式(1)对于a=k 1也成立，若k 1是素数，式(1)

7、显成立.如果k 1是合数，则存在素数p与整数d，使得k 1=pd.由于2 d k，由归纳假定知存在素数q1,q2,ql，使得d=q1q2ql，从而k 1=pq1q2ql.从而由归纳法推出式(1)对任何大于1的整数a成立。证毕。,2023/9/5 22:14,推论,任何大于1的合数a必有一个不超过a1/2的素因数。证明 由于 a是合数，故存在整数 b和 c使 abc,其中:1ba,1ca.若b和c均大于a1/2,则abca1/2a1/2a,这是不可能的.因此b和c中必有一个小于或等于a1/2.,2023/9/5 22:14,例5 写出不超过100的所有的素数.,解 将不超过100的正整数排列如下

8、：1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 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,2023/9/5 22:14,按

9、以下步骤进行：,()删去1，剩下的后面的第一个数是2，2是素数；()删去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整除的数以后，就得到了不超过100的全部素数.,2023/9/5 22:14,在例5中所使用的寻找素数的方法,称为Eratosthenes筛法.它可以用来求出不超过任何固定整数的所有素数.在理论

10、上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的.,2023/9/5 22:14,定理7.(Euclid)素数有无穷多个.,证明：(反证法)假设素数是有限多个,共有n个,令它们是p1,p2,pn,并令a=p1p2pn+1.若a是素数,则因api，其中1in,故素数个数最少是n+1个,这与假设素数个数为n个矛盾.若a 不是素数,则由定理4知,a 的大于 1的最小因数b是素数.由于pi|p1p2pn,但 pi 不能整除1,故pi不能整除a,因此 bpi,其中1in,那么a也为素数.所以在p1,p2,pn,还有素数,这也与已知共有n个素数矛盾.,2023/9/5 22:

11、14,最大公因数与最小公倍数,2023/9/5 22:14,定义3 最大公因数,设al,a2,ak和d都是整数,k2.若d|ai，1ik,则称d是al,a2,ak的公因数.所有公因数中最大的那一个数，称为al,a2,ak的最大公因数,记为(al,a2,ak).由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。显然，(a,1)=1，(a,0)=|a|，(a,a)=|a|；,2023/9/5 22:14,定理8 下面的等式成立：,()（a1,a2)=(a2,a1)=(-a1,a2)；一般地(a1,a2,ai,ak)=(ai,a2,a1,ak)=(-a1,a2,ak)=(|

12、a1|,|a2|,|ak|)；()若a1|aj,j=2,k,则（a1,a2)=(a1,a2,ak)=(a1)=|a1|()对任意整数x，(a1,a2)=(a1,a2,a1x)(a1,ak)=(a1,ak,a1x)；()对任意整数x,（a1,a2)=(a1,a2+a1x)(a1,a2,a3,ak)=(a1,a2+a1x,a3,ak)；()若p是素数,则(p,a)=1或pa；一般地（p,a1,ak)=1或pa.,2023/9/5 22:14,例5,2023/9/5 22:14,定义5 互素,如果(a1,a2,ak)=1，则称a1,a2,ak是互素的（或互质的）；如果(ai,aj)=1，1 i,j

13、k，i j，则称a1,a2,ak是两两互素的（或两两互质的）.显然，a1,a2,ak两两互素可以推出(a1,a2,ak)=1，反之则不然，例如(2,6,15)=1，但(2,6)=2.,2023/9/5 22:14,定理 9,(a1,a2,ak)=1的充要条件是存在整数x1,x2,xk，使得a1x1 a2x2 akxk=1.充分性 若式(1)成立，如果(a1,a2,ak)=d 1，那么由dai（1 i k）推出d a1x1 a2x2 akxk=1，这是不可能的.所以有(a1,a2,ak)=1.证毕.,2023/9/5 22:14,定理 10,设正整数m|(a1,a2,ak).我们有m(a1/m,

14、a2/m,ak/m)=(a1,a2,ak)特别地有=1.,2023/9/5 22:14,定义 6 最小公倍数,设a1,a2,ak和m都是整数,k2.若ai|m,1ik,则称m是a1,a2,ak的公倍数.在a1,a2,ak所有公倍数中最小的那一个正整数,称为a1,a2,ak的最小公倍数,记为 a1,a2,ak.,2023/9/5 22:14,定理 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,a2,da1,a2,ak=a1,a2,ak

15、,d,2023/9/5 22:14,定理12,设m0,我们有ma1,mak=ma1,ak,2023/9/5 22:14,3 带余除法与辗转相除法,2023/9/5 22:14,定理1 带余数除法,设a与b是两个整数，a 0,则存在唯一的两个整数q和r，使得 b=aq r，0 r|a|(1)证明 存在性 若ab，b=aq，qZ，可取r=0.若a b，考虑集合 A=b ka；kZ，在集合A中有无限多个正整数，设最小的正整数是r=b k0a，则必有 0|a|，即 b k0a|a|，b k0a|a|0，这样,在集合A中,又有正整数r1=b k0a|a|r，这与r的最小性矛盾。,2023/9/5 22:

16、14,所以式(2)必定成立.取q=k0 知式(1)成立.存在性得证.唯一性 假设有两对整数q、r 与q、r 都使得式(1)成立，即b=q a r=q a r，0 r,r|a|，则(q q)a=r r，|r r|a|，(3)因此r r=0，r=r，再由式(3)得出q=q，唯一性得证.证毕.,2023/9/5 22:14,定理2,设a与b是两个整数，a 0，设d是一给定的整数.那么，一定存在唯一的两个整数q1和r1，使得 b=aq1 r1，d r1|a|+d(4)此外，ab的充要条件是ar1.,2023/9/5 22:14,定义1,称式(1)中的q是b被a除的商，r是b被a除的最小非负余数。式(4

17、)中的r1统称为余数.由定理1可知，对于给定的整数a，可以按照被a除的余数将所有的整数分成a类。在同一类中的数被a除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究。,2023/9/5 22:14,推论3,设a0.任一整数被 a 除后所得的最小非负余数是且仅是0,1,a-1这a个数中的一个.由此全体整数按被a除后所得的最小非负余数可分为两两不相交的a个类.0moda,1moda,(a-1)modaa=2时，全体整数分为两类：0mod2，1mod2,2023/9/5 22:14,例2,()0mod2 0mod3=0mod6;()1mod2 1mod3=1mod6；()0m

18、od2 1mod3=4mod6.例31mod2=1mod63mod65mod6,2023/9/5 22:14,例4 a进位表示,设a 2是给定的正整数.那么，任一正整数n必可唯一表为 n=rkak+rk-1ak-1+r1a+r0,(4)其中整数k 0，0 rj a-1，(0 j k)，rk0.这就是正整数的a进位表示.,2023/9/5 22:14,例5,设a2是奇数.证明：()一定存在正整数d a-1,使得a|2d-1.()设d0是满足()的最小正整数d.那么，a|2h-1(hN)的充要条件是 d0|h.()必有正整数d使得（2d-3,a)=1.,2023/9/5 22:14,定理4(Euc

19、lid)欧几里德算法.,设 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.,2023/9/5 22:14,证明:由于|b|r1r2rn0,故欧几里德算法中的带余除法必在有限步内得到一个余数是零的等式,即rn+1=0.根据前面定理可知：(a,b)=(b,r1)=(rn-1,rn)=(rn,0)=rn.欧几里德算法也称辗转相除法.,2023/9/5 22:14,在Euclid算法中,

20、由: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代入上式,如此继续下去,最后得到:rn=sa+tb,其中 s和t是整数.于是有(a,b)是 a和b线性组合表示定理.定理5()若任给整数 a,b,则存在整数x和 y,使得(a,b)=ax+by.容易证明下面结论()a和b的公因数整除(a,b).,2023/9/5 22:14,例6,用欧几里德算法求(1997,57).用1997和57的线性组合表示(1997,57)求1997和57的所有公因数解 用下划线标识余数 19975735+

21、2 57228+1 2l2+0因此,(1997,57)=l,即1997和57是互素的.,2023/9/5 22:14,1=57-228=57-(1997-5735)28=-281997+(57+573528）=-281997+98157由于1997和57是互素的,公因数只有1和-1.,2023/9/5 22:14,例7,设m,n是正整数.证明（2m-1,2n-1)=2(m,n)-1,2023/9/5 22:14,4 最大公因数理论,2023/9/5 22:14,定理1 aj|c(1j k)的充要条件是a1,ak|c,证明：充分性显然.必要性，设a1,ak=m.c是a1,ak的任一公倍数,利用带

22、余除法得: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,2023/9/5 22:14,定理2,设D是正整数.那么D=（a1,a2,ak）的充要条件是：()D|aj(1 j k);()若daj(1 j k),则d(a1,a2,ak).这个结论表明：公约数一定是最大公约数的约数。,2023/9/5 22:14,定理3,(ma1,ma2,mak)=|m|(a1,a2,ak).定理 4()(a1,a2,ak)=(a1,a2),

23、a3,ak)；()(a1,a2,ak+r)=(a1,ak),(ak+1,ak+r)；推论（a1,a2)(b1,b2)=(a1b1,a1b2,a2b1,a2b2),2023/9/5 22:14,定理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.,2023/9/5 22:14,定理6,对于任意的整数a，b，m，下面的结论成立：()由mab及(m,a)=1可以推出mb；()由m1n，m2n及(m1,m2)=1可以推出m1m2n.一般地，若m1,m2,mk两两

24、互素，及mjn(1 j k），则m1 m2 mk n.证明：()(m,a)=1，则(m,ab)=(m,b)，由mab，(m,ab)=|m|，故(m,b)=|m|，从而mb.()m1n知n=m1n1,m2n,即m2m1n1,又(m1,m2)=1,知m2n1，因而m1m2n.,2023/9/5 22:14,定理7,设a1和a2是正整数,且(a1,a2)=d,a1,a2=m,则a1a2md.,2023/9/5 22:14,例1,设p是素数.证明：()p|，1 j p-1()对任意的正整数a,p|ap-a;()若(p,a)=1，则p|ap-1-1.例2 证明：()(a,uv)=(a,(a,u)v);()(a,uv)|(a,u)(a,v),2023/9/5 22:14,例3,设k是正整数.若一个有理数的k次方是整数，那么，这个有理数一定是整数.,2023/9/5 22:14,例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,使得mad-1;()设d0是满足()的最小正整数d，那么，mah-1(h1)的充要条件是d0|h.,