初等数论全套教案.doc

第一章 整除理论 整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。 第一节 数的整除性 定义1 设a，b是整数，b ( 0，如果存在整数c，使得 a = bc 成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号b(a；如果不存在整数c使得a = bc成立，则称a不被b整除，记为ba。 显然每个非零整数a都有约数 (1，(a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。 被2整除的整数称为偶数，不被2整除的整数称为奇数。 定理1 下面的结论成立： (ⅰ) a(b ( (a((b； (ⅱ) a(b，b(c ( a(c； (ⅲ) b(ai，i = 1, 2, (, k ( b(a1x1 ( a2x2 ( ( ( akxk，此处xi（i = 1, 2, (, k）是任意的整数； (ⅳ) b(a ( bc(ac，此处c是任意的非零整数； (ⅴ) b(a，a ( 0 ( |b| ( |a|；b(a且|a| |b| ( a = 0。 证明 留作习题。 定义2 若整数a ( 0，(1，并且只有约数 (1和 (a，则称a是素数（或质数）；否则称a为合数。 以后在本书中若无特别说明，素数总是指正素数。 定理2 任何大于1的整数a都至少有一个素约数。 证明 若a是素数，则定理是显然的。 若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1, d2, (, dk 。d1是其中最小的。d1不是素数，则存在e1 1，e2 1，d1 = e1e2，，e1e2也是a的正的非平凡约数。d1的最小性矛盾。d1是素数。 推论 任何大于1的合数a必有一个不超过的素约数。 证明 使用定理2中的记号，a = d1d2，d1 1是最小的素约数，所以d12 ( a。证毕。 例1 设r是正奇数，n，有 n ( 21r ( 2 r ( ( ( n r。 解 对于任意的正整数a，b以及正奇数k，有 ak ( bk = (a ( b)(ak ( 1 ( ak ( 2b ( ak ( 3b2 ( ( ( bk ( 1) = (a ( b)q， 其中q是整数。s = 1r ( 2 r ( ( ( n r， 2s = 2 ( (2 r ( n r) ( (3 r ( (n ( 1)r) ( ( ( (n r ( 2 r) = 2 ( (n ( 2)Q， Q是整数。n ( 2(s，由上式知n ( 2(2，因为n ( 2 2，n ( 2s。2 设A = { d1, d2, (, dk }是n的所有约数的集合，B = 也是n的所有约数的集合。 解 由以下三点理由可以证得结论： (ⅰ) A和B的元素个数相同； (ⅱ) 若di(A，即di(n，n，反之亦然； (ⅲ) 若di ( dj，。 例3 以d(n)表示n的正约数的个数，例如：d(1) = 1，d(2) = 2，d(3) = 2，d(4) = 3，(d(1) ( d(2) ( ( ( d(1997) 是否为偶数？ 解 对于n的每个约数d，都有n = d(，n的正约数d与是成对地出现的。d =，即n = d2时，d才是同一个数。n是完全平方数时，d(n)是奇数。 因为442 1997 452，d(1), d(2), (, d(1997)中恰有44个奇数，d(1) ( d(2) ( ( ( d(1997)是偶数。 例4 设凸2n边形M的顶点是A1, A2, (, A2n，O在M的内部，1, 2, (, 2n将M的2n条边分别编号，OA1, OA2, (, OA2n也同样进行编号，，OA1A2, OA2A3, (, OA2nA1的周长都相等。 解 假设这些三角形的周长都相等，s。 2ns = 3(1 ( 2 ( ( ( 2n) = 3n(2n ( 1)， 即 2s = 3(2n ( 1)， 2(3(2n ( 1)，，k ( 1，证明： (ⅰ) 若2k ( n 2k ( 1，1 ( a ( n，a ( 2k，2ka； (ⅱ) 若3k ( 2n ( 1 3k + 1，1 ( b ( n，2b ( 1 ( 3k，3k2b ( 1。 解 (ⅰ) 若2k|a，则存在整数q，使得a= q2k。显然q只可能是0或1。此时a= 0或2k ，这都是不可能的，所以2ka； (ⅱ) 若 3k|2b-1，q，使得2b-1= q3k，显然q只可能是0，1, 或2。此时2b-1= 0，3k，或，这都是不可能的，所以3k2b ( 1。 例6 写出不超过100的所有的素数。 解 将不超过100的正整数排列如下： 1 2 3 4 5 6 7 8