《数论算法》教案(整数的可除性).docVIP

整数的可除性 内容 整除性 公因数、最大公因数 辗转相除法（欧几里得除法） 算术基本定理 要点 培养对数论问题的认识及证明问题的思路 《数论》从研究整数开始，叫“整数论”。经进一步发展，叫做“数论”。 确切地说，数论是研究整数性质的学科。 自然数（正整数）负整数0（统称整数）。 算术运算：加、减、乘、除（四则运算）。 加法、减法和乘法在整数范围内可以毫无阻碍地进行。但整数之间的除法在整数范围内并不一定能够无阻碍地进行。 《数论算法》主要从应用角度出发，研究数论问题中实用的方法和技术。 整除的概念 欧几里得除法 整除概念 【定义1.1.1】 设a, b∈Z（整数集合），b≠0，如果存在q∈Z，使得a＝bq，则称b整除a或a可被b整除，记作b│a，且称a是b的倍数，b是a的因数（也可称为除数、约数、因子）。否则，称b不能整除a或a不能被b整除，记作ba。 说明： q也是a的因数，并将q写为a/b或； 当b遍历整数a的所有因数时，－b也遍历整数a的所有因数； 当b遍历整数a的所有因数时，a/b也遍历整数a的所有因数。 例：设 a＝6，则有 当b＝3时，q＝2＝6/3 当b＝1, 2, 3, 6,－1,－2,－3,－6时有－b＝－1,－2,－3,－6, 1, 2, 3, 6 当b＝1, 2, 3, 6, －1,－2,－3,－6时有a/b＝6, 3, 2, 1, －6,－3,－2,－1 【特例】： 0是任何非零整数的倍数； ±1是任何整数的因数； 任何非零整数a是其自身的倍数，也是其自身的因数。 性质 设，则 │。 （证） a＝bq －a＝q(－b) 其余类推。 【例1.1.1】30的所有因数：±1，±2，±3，±5，±6，±15，±30 传递性：， （证）且 b＝c，a＝b a＝c c│a。 ，，则 ，，则对任意整数s、t，有 推广： 若，，则a＝±b （证） a＝b b＝a a＝ ＝1 ＝±1 （c≠0） 若，则 ≤ 例 【例1.1.2】证明：若且，则。 （证） 已知 。 。即m＝7q 所以 n＝3(7q)＝21q 。 【例1.1.3】设。若，则。 （证） 又 ＝(an＋n)－an＝n，即 （由a＝2t－1知2t＝a＋1，从而2tn＝an＋n） 【例1.1.4】设a, b是两个给定的非零整数，且有整数x, y，使得。证明：若且，则 （证） 由且 。 ＝n(ax＋by)，即。 注意到，由此也证明了例1.1.2。 【例1.1.5】设是整系数多项式。若，则 （证） 由及 ＝ （k＝1, 2, …, n） ∴ 。 应用：若，那么。 例：设，判断7能否整除。 因 ＝7q＋4，故只需判断： ＝＝3082？ 答：不能 素数 定义（素数与合数） 设整数p≠0, ±1。如果它除了显然约数±1, ±p外没有其它的约数，那么，就称为素数（或质数、不可约数）。若a≠0, ±1，且不是素数，则称为合数。 约定：素数一般指正整数。 性质 最小正因数必是素数 n是正整数，当2≤p≤且pn，则n是素数。 素数有无穷多。 （证）（c）：用反证法。 假设只有有限个素数：。构造 则 且a≠（i＝1, 2, …, k）。 ∴ a必是合数 存在素数p，使得 。 由假设知p等于某个 一定整除 但素数，矛盾。 因此，假设是错误的，即素数必有无穷多个。 性质（b）的应用：快速判断素数。 扩展：设是全体素数按大小顺序排成的序列，以及 。直接计算可得： ， ， ， ， ， ， ， ， ， 前五个是素数，后五个是合数，但都有一个比更大的素因数。 未解决的问题：至今还不知道是否有无穷多个k使是素数，也不知道是否有无穷多个k使是合数。 欧几里德除法 也叫带余数除法、除法算法 初等数论的证明中最重要、最基本、最常用的工具之一。 欧几里德除法： 设a, b是两个给定的整数，b≠0。那么，一定存在唯一的一对整数q与r，满足 , 约定：b0。上式可表为 , （2） 存在性 当时，可取，r＝0。 当ba时，考虑集合 ＝{……，－3b，－2b，－b，0，b，2b，3b，……} 将实数分为长度为b的区间，a必落在某区间内，即存在整数q，使得 qb≤a＜(q＋1)b 令r＝a－bq，则有 , 唯一性 设有也满足（2）式，即 必有 当q≠时有 ≥b， 矛盾，故必有，。 推论：的充要条件是r＝0。 当a＝qb＋r时, 有。 当满足时，就有 r＝0。 一般形式 设a, b是两个给定的整数，，则对任意整数c，一定存在唯一的一对整数q与r，满足 , （3） 此外，的充要条件是。 例：a＝100，