初等数论第一章整除1-4.ppt

2019/7/20 07:19,初等数论 教师：何艳,2019/7/20 07:19,数论的基本内容,按照研究方法的不同，数论可分为 初等数论 解析数论 代数数论 几何数论,2019/7/20 07:19,参考书目,1、南基洙主编初等数论； 2、柯召、孙琦编著数论讲义，高等教育 出版社； 3、闵嗣鹤、严士健编初等数论，高等教 育出版社； 4、郑克明主编初等数论，西南师范大学 出版社。,2019/7/20 07:19,初等数论,第一章 整除 1 自然数与整数,2019/7/20 07:19,归纳原理,设S是N的一个子集，满足条件： ()1S; ()如果n S，则n+1 S, 那么，S=N.,2019/7/20 07:19,定理1 数学归纳法,设P(n)是关于自然数n的一种性质或命题.如果 ()当n=1时，P(1)成立； ()由P(n)成立必可推出P(n+1)成立， 那么， P(n)对所有自然数n成立.,2019/7/20 07:19,定理2 最小自然数原理,设T是N的一个非空子集. 那么，必有t0 T, 使对任意的t T有t0t，即t0是T中的最小 自然数.,2019/7/20 07:19,定理3 最大自然数原理,设M是N的非空子集.若M有上界，即存在 aN, 使对任意的m M有m a, 那么必 有m0 M，使对任意的m M有m m0， 即m0是M中的最大自然数。,2019/7/20 07:19,定理4 第二数学归纳法,设 P(n) 是关于自然数 n 的一种性质或命题. 如果() 当 n=1 时， P(1) 成立； ()设 n1. 若对所有的自然数 mn, P(m)成立， 则必可推出P(n)成立，那么, P(n) 对所有 自然数 n 成立.,2019/7/20 07:19,定理5 鸽巢原理,设n是一个自然数.现有n个盒子和n+1个物体. 无论怎样把这n+1个物体放入这n个盒子中， 一定有一个盒子中被放了两个或两个以上的 物体。,2019/7/20 07:19,2 整除,2019/7/20 07:19,定义1,设a，b是整数，a 0，如果存在整数q， 使得b = aq，则称b可被a整除，记作ab ， 且称b是a的倍数，a是b的约数(因数、除数)； 如果不存在整数q使得b = aq成立，则称b不被 a整除，记为a b。 被2整除的数称为偶数，不被2整除的称为奇数,2019/7/20 07:19,定理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.,2019/7/20 07:19,例1 证明：若3|n且7|n，则21|n. 例2 设a=2t-1. 若a|2n, 则a|n. 例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).,2019/7/20 07:19,定义2,显然每个非零整数a都有约数 1，a，称 这四个数为a的显然因数，a的另外的因数 称为非显然因数。 若整数a 0，1，并且只有约数 1和 a， 则称a是素数（或质数）；否则称a为合数。 以后在本书中若无特别说明，素数总是指 正素数。,2019/7/20 07:19,定理2,设A = d1, d2, , dk 是n的所有约数的集合，则 B = 也是n的所有约数的集合。 解 由以下三点理由可以证得结论： () A和B的元素个数相同； () 若diA，即din，则 n，反之亦然； () 若di dj，则 .,2019/7/20 07:19,定理3,() a1是合数的充要条件是 a=de,11, q是不可约数且d|q, 则d=q. 定理4 若a是合数，则必有不可约数p|a.,2019/7/20 07:19,定理5 设整数a2, 那么a一定可表为素数的乘积,(包括a本身是素数)，即 a=p1p2 ps其中pj（1j s) 是素数. 证明 当a = 2时，结论显然成立。 假设对于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成立。 证毕。,2019/7/20 07:19,推论,任何大于1的合数a必有一个不超过a1/2的素 因数。 证明 由于 a是合数，故存在整数 b和 c使 abc, 其中: 1ba, 1ca. 若b和c均大于 a1/2 , 则abca1/2a1/2a, 这是不可能的. 因此b和c中必有一个小于或等于a1/2.,2019/7/20 07:19,例5 写出不超过100的所有的素数.,解 将不超过100的正整数排列如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100,2019/7/20 07:19,按以下步骤进行：,() 删去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的全部素数.,2019/7/20 07:19,在例5中所使用的寻找素数的方法,称为 Eratosthenes筛法.它可以用来求出不超 过任何固定整数的所有素数.在理论上这 是可行的；但在实际应用中，这种列出 素数的方法需要大量的计算时间，是不 可取的.,2019/7/20 07:19,定理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个素数矛盾.,2019/7/20 07:19,最大公因数与最小公倍数,2019/7/20 07:19,定义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|；,2019/7/20 07:19,定理8 下面的等式成立：,() （a1 , a2)=(a2 , a1)=(-a1 , a2) ；一般地 (a1 , a2 , , ai , , ak) = (ai , a2 , , a1 , , ak) = (-a1 , a2 , , ak)=(|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 .,2019/7/20 07:19,例5,2019/7/20 07:19,定义5 互素,如果(a1 , a2 , ak) = 1，则称a1 , a2 , ak是互 素的（或互质的）； 如果(ai , aj) = 1，1 i, j k，i j，则称a1 , a2 , , ak是两两互素的（或两两互质的）. 显然，a1 , a2 , , ak两两互素可以推出 (a1 , a2 , , ak) = 1，反之则不然，例如 (2, 6, 15) = 1，但(2, 6) = 2.,2019/7/20 07:19,定理 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 . 证毕 .,2019/7/20 07:19,定理 10,设正整数m| (a1 , a2 , , ak) . 我们有 m (a1/m, a2/m, , ak/m) = (a1 , a2 , ak) 特别地有 = 1 .,2019/7/20 07:19,定义 6 最小公倍数,设a1 , a2 , ak和m都是整数, k2 . 若ai|m , 1ik, 则称m是a1 , a2 , , ak的公倍数. 在a1 , a2 , ak所有公倍数中最小的那一个 正整数, 称为a1 , a2 , , ak的最小公倍数, 记为 a1 , a2 , ak .,2019/7/20 07:19,定理 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|a1 a1 , a2=a1 , a2 , d a1 , a2 , , ak= a1 , a2 , , ak , d,2019/7/20 07:19,定理12,设m0, 我们有 ma1 , , mak=ma1 , , ak,2019/7/20 07:19,3 带余除法与辗转相除法,2019/7/20 07:19,定理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的最小性矛盾。,2019/7/20 07:19,所以式(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 ，唯一性得证. 证毕.,2019/7/20 07:19,定理2,设a与b是两个整数，a 0，设d是一给定 的整数. 那么，一定存在唯一的两个整数 q1和r1，使得 b = aq1 r1，d r1 |a| +d (4) 此外， ab的充要条件是ar1 .,2019/7/20 07:19,定义1,称式(1)中的q是b被a除的商，r是b被a除的最 小非负余数。式(4)中的r1统称为余数. 由定理1可知，对于给定的整数a，可以按照 被a除的余数将所有的整数分成a类。在同一 类中的数被a除的余数相同。这就使得许多关 于全体整数的问题可以归化为对有限个整数 类的研究。,2019/7/20 07:19,推论3,设a0. 任一整数被 a 除后所得的最小非负余 数是且仅是0 , 1 , , a-1这a个数中的一个. 由此全体整数按被a除后所得的最小非负余数 可分为两两不相交的a个类. 0moda , 1moda , , (a-1)moda a=2时，全体整数分为两类： 0mod2， 1mod2,2019/7/20 07:19,例2,() 0mod2 0mod3=0mod6; () 1mod2 1mod3=1mod6； () 0mod2 1mod3=4mod6. 例3 1mod2=1mod63mod65mod6,2019/7/20 07:19,例4 a进位表示,设a 2是给定的正整数. 那么，任一正整数n 必可唯一表为 n=rkak+rk-1ak-1+ +r1a+r0, (4) 其中整数k 0，0 rj a-1，(0 j k)， rk0. 这就是正整数的a进位表示 .,2019/7/20 07:19,例5,设a2是奇数. 证明： () 一定存在正整数d a-1 , 使得a|2d-1. () 设d0是满足()的最小正整数d. 那么， a|2h-1 (hN) 的充要条件是 d0|h. () 必有正整数d使得（2d-3 , a)=1.,2019/7/20 07:19,定理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.,2019/7/20 07:19,证明: 由于 |b|r1r2rn0, 故欧几里 德算法中的带余除法必在有限步内得到一个 余数是零的等式, 即rn+1=0. 根据前面定理可知： (a,b)=(b,r1)=(rn-1,rn)= (rn,0)=rn. 欧几里德算法也称辗转相除法.,2019/7/20 07:19,在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代入 上式, 如此继续下去, 最后得到 : rn=sa+tb, 其中 s和t是整数. 于是有(a,b)是 a和b线性组合表示定理. 定理5 () 若任给整数 a, b, 则存在整数x和 y, 使得 (a,b)= ax+by. 容易证明下面结论 () a和b的公因数整除(a,b).,2019/7/20 07:19,例6,用欧几里德算法求(1997,57). 用1997和57的线性组合表示(1997,57) 求1997和57的所有公因数 解 用下划线标识余数 19975735 + 2 57228 + 1 2l2 + 0 因此, (1997,57)=l, 即1997和57是互素的.,2019/7/20 07:19, 1=57-228 =57-(1997-5735)28 =-281997+(57+573528） =-281997+98157 由于1997和57是互素的, 公因数只有1和-1.,2019/7/20 07:19,例7,设m,n是正整数.证明 （2m-1,2n-1)=2(m,n)-1,2019/7/20 07:19,4 最大公因数理论,2019/7/20 07:19,定理1 aj|c (1j 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,2019/7/20 07:19,定理2,设D是正整数.那么D =（a1, a2, , ak）的充要 条件是： () D| aj(1 j k); () 若daj (1 j k), 则d(a1, a2, , ak). 这个结论表明：公约数一定是最大公约数的 约数。,2019/7/20 07:19,定理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,a2b1,a2b2),2019/7/20 07:19,