初等数论1 - 整除理论课件.ppt

整 除 理 论;1、素数 (1)、素因子 (2)、素数分布 (3)、素数搜寻 (4)、素性判定 2、GCD和LCM;定义 若整数a ? 0，?1，并且只有约数 ?1和 ?a，则称a是素数（或质数）； 否则称a为合数。 定理 任何大于1的整数a都至少有一个素约数。 推论 任何大于1的合数a必有一个不超过a1/2的素约数。 定理 (算术基本定理) 任何大于1的整数n可以唯一地表示成(标准分解式) 其中p1 , p2, ? , pk 是素数，p1 p2 ? pk，?1, ?2, ?, ?k是正整数。 哥德巴赫猜想：“每个大于2的偶数均可表成为两个素数之和” 陈景润： “每一个充分大的偶数都可表为一个素数及一个不超过两个素数乘积之和” ;素数分布;素数分布;素数分布;素数搜寻;素性判定;GCD和LCM;GCD和LCM;带余数除法 设a与b是两个整数，b ? 0，则存在唯一的两个整数q和r，使得 a = bq ? r，0 ? r |b|。 定理 若a = bq ? r，则(a, b) = (b, r)。实际上给出一个求最大公因子的方法。 推论 设a1, a2, ?, an为不全为零的整数，以y0表示集合 A = { y：y = a1x1 ? ? ? anxn，xi?Z，1 ? i ? n } 中的最小正数，则 对于任何y?A， y0?y； 特别地， y0?ai，1 ? i ? n。 证明： 设y0 = a1x1? ? ? ? anxn?， 对任意的y = a1x1 ? ? ? anxn?A，存在q, r0?Z，使得 y = qy0 ? r0，0 ? r0 y0 。 因此 r0 = y ? qy0 = a1(x1 ? qx1?) ? ? ? an(xn ? qxn?)?A。 如果r0 ? 0，那么，因为0 r0 y0，所以r0是A中比y0还小的正数， 这与y0的定义矛盾。所以r0 = 0，即y0?y。 显然ai?A（1 ? i ? n），所以y0整除每个ai（1 ? i ? n）。;定理 设a1, a2, ?, ak ?Z，记 A = { y：y = ，xi?Z，? ? i ? k }。 如果y0是集合A中最小的正数，则y0 = (a1, a2, ?, ak)。 推论 设d是a1, a2, ?, ak的一个公约数，则d?(a1, a2, ?, ak)。 最大公约数不但是公约数中的最大的，而且是所有公约数的倍数。 定理 记d = (a1, a2, ?, ak)，则 (a1/d, a2/d, ?, ak/d)=1。 特别地, (a/(a,b), b/(a,b)=1 。 定理 (a1, a2, ?, ak) = 1的充要条件是存在整数x1, x2, ?, xk，使得 a1x1 ? a2x2 ? ? ? akxk = 1。 定理 对于任意的整数a，b，c，下面的结论成立： (ⅰ) 由b?ac及(a, b) = 1可以推出b?c； (ⅱ) 由b?c，a?c及(a, b) = 1可以推出ab?c。 推论 若p是素数，则下述结论成立： (ⅰ) p?ab ? p?a或p?b； (ⅱ) p?a2 ? p?a。;推论 若 (a, b) = 1，则(a, bc) = (a, c)。 （备注1） 推论 若 (a, bi) = 1，1 ? i ? n，则(a, b1b2?bn) = 1。 定理 对于任意的n个整数a1, a2, ?, an ，记