§初等数论整除.pptVIP

阜阳师范学院 数科院 初等 数论 推论2 证明： 另解：利用推论1 . 思考题：用辗转相除法求x，y，使得 125x ? 17y = (125, 17). 习题选讲 4、证明：在辗转相除法中的n满足： 证：由P3§1习题4知： §1.3 最小公倍数 定义1 ： 整数a1, a2, ?, ak的公共倍数称为a1, a2, ?, ak 的公倍数。a1, a2, ?, ak的正公倍数中的最小的一个叫 做a1, a2, ?, ak的最小公倍数，记为[a1, a2, ?, ak]. 定理1： 下面的等式成立： (ⅰ) [a, 1] = |a|，[a, a] = |a|； (ⅱ) [a, b] = [b, a]； (ⅲ) [a1, a2, ?, ak] = [|a1|, |a2| ?, |ak|]； (ⅳ) 若a?b，则[a, b] = |b|。 定理2 对任意的正整数a，b，有 证明： 设m是a和b的一个公倍数， 那么存在整数k1，k2，使得m = ak1，m = bk2， 因此 ak1 = bk2 . 推论1 两个整数的任何公倍数一定是 最小公倍数的倍数。 推论2 设m，a，b是正整数，则[ma, mb] = m[a, b]。 定理3 注：把多个整数的公倍数化为两个数的公倍数来计算。 推论 若m是a1, a2, ?, an的公倍数，则[a1, a2, ?, an]?m 。 定理4 整数a1, a2, ?, an两两互素， 即(ai, aj) = 1，1 ? i, j ? n，i ? j 的充要条件是 [a1, a2, ?, an] = a1a2?an . 例3 设a，b，c是正整数，证明 [a, b, c](ab, bc, ca) = abc 。 证：[a, b, c] = [[a, b], c] = (ab, bc, ca) = (ab, (bc, ca)) = (ab, c(a, b)) 代入即得证. 多项式的带余式除法 称为n次多项式. 注：整数的带余数除法推广到多项式的带余式除法， 其他方面的性质〔整除的性质、辗转相除法、约数、 倍数等〕也可以作类似地推广。 习题讲解： 构造方程 其有理根只能为 §1.4 质数 算术基本定理 一、质数与合数 定义：若整数a ? 0，?1，并且只有约数 ?1和 ?a，则 称a是素数（或质数）；否则称a为合数。 注：本书中若无特别说明，素数总是指正素数。 定理1 设a是大于1的整数，则 （1）a 除1外的最小正因数q是质数； （2）若a是合数，则 求质数的方法 例1 求30以内的质数. 划去2、3、5的倍数，得到不能被2、3、5整除的数有 7、11、13、17、19、23、29. 所以30以内的质数有 2、3、5、7、11、13、17、19、23、29. 该方法称为幼拉脱斯展纳筛法，利用该方法可以 构造质数表，祥见教材P17-18. 分析：利用定理2反证即得. 注意：在推论中，若p不是质数，则结论不能成立。 二、算术基本定理 定理3〔算术基本定理〕任一大于1的整数n能表示成 质数的乘积，且其分解的结果是唯一的[不考虑次序]. 即有： n = p1p2?pm (1) 其中pi（1 ? i ? m）是素数. 证明 当n = 2时，结论显然成立。 由于2 ? d ? k，由归纳假定知存在素数q1, q2, ?, ql， 使得d = q1q2?ql，从而k ? 1 = pq1q2?ql。 假设对于2 ? n ? k，式(1)成立，下证式(1)对于 n = k ? 1也成立， 从而由归纳法推出式(1)对任何大于1的整数n成立。 如果k ? 1是素数，式(1)显然成立。 若k ? 1是合数，则存在素数p与整数d，使得k ? 1 = pd。 推论3.1〔标准分解式〕 推论3.2 a的正因数可以表示为a的分解式中的部分 因数的乘积。 推论3.3 设a,b是任意两个正整数，且 推论3.3是分解质因数方法求最大公因数和最小公倍数的依据。 定理4 质数的个数是无穷的。 证：假设质数的个数有限，记为 所以存在质数p, 所以，质数的个数是无穷的。 例2 写出51480的标准分解式。 解：51480 = 2?25740 = 22?12870 = 23?5?1287 = 23?5?3?429 = 23?5?32?143 = 23?32?5?11?13。 = 23?6435 * * 第一章 整数的可除性 整除性理论是初等数论的基础，本章要介绍 带余数除法，辗转相除法，最大公约数，最小公 算术基本定理以及 倍数， 它们的一些应用。 中小学数学中的一些数论问题： 4.已知: 782 + 8161能被57整除，求证：783 +8163也能