第一讲：整除,带余除法,辗转.pptVIP

专业基础课程 初等数论 Number Theory 邯郸学院数学系 石立叶 初等数论 前言 第一章 整数的整除性 第一节 整除的概念 带余除法 定义 设a,b是任意两个整数，其中 如果存在一个整数q，使得 (1)成立， 我们就说b整除a,或a能被b整除，记 作： ，b叫做因数，a叫做倍数。 若这样的q不存在，则称b不能整除a,或a 不能被b整除，记做b a 定理1 若 ，则 证 ： 定理2： 若 定理3： 若 例 若n是奇数，则8?n2 ? 1。 解 设n = 2k ? 1，则 n2 ? 1= (2k ? 1)2 ? 1 = 4k(k ? 1)，在k和k ? 1 中有一个是偶数，所以8? n2 ? 1 例 以d(n)表示n的正约数的个数，例如： d(1) = 1，d(2) = 2，d(3) = 2，d(4) = 3，? 问：d(1) ? d(2) ? ? ? d(1997)是否为偶数？ 提示：442 1997 452 带余除法： 若a和b是两个整数，其中b0,则存在两个 整数q及r,使得 （2） 成立，而且q及r 是唯一的 q叫做a被b整除所得的不完全商，r叫做a被 b整除所得的余数 注：带余除法要注意两点:b0 例：a=255,b=15,求商和余数 a=417,b=15,求商和余数 a=-81,b=15,求商和余数 例：a是两位数，a除310的余数为37，则a=? 例：证明 ，其中n是任何整数 第一节 整除的概念 带余除法 回顾： 第二节 最大公因数与辗转相除法 定义 设 是 个整 数，若d是它们之中每一个的因数，那末d就 叫做 的一个公因数 最大公因数 整数 的公因数中 最大的一个，记作： 若 =1，我们说 互素，或互质 若每两个整数互质，两两互质 定理1：若 是任意n个不全为 零的整数，则 (1) 与 的公因数 相同 (2) 例:(6,-4)=(6,4) 所以，我们只要讨论非负整数的公 因数， 设a,b是非负整数，分情况： (1)两个都为零 最大公因数不存在 (2)有一个为零 设a=0,（a,b）=(0,b)=b (3)两个都不为零 即 定理3 设a,b,c是任意三个不全为零的整数，且 a=bq+c,q是不等于零的整数，则a,b和b,c的公因 数相同，因而(a,b）=(c,b) 两个都不为零 (1) (2)a不整除b，或b不整除a 定理4 若a和b是任意两个整数，则(a,b) 等于(2)式中倒数第一个不为零的余数，即 （2）式所提供求最大公因数的方法叫做辗转相除法，也称欧几里德算法 例 求(1859,1573) 例 求(169,121) 例 ①用欧几里德算法求(1997,57). ②用1997和57的线性组合表示(1997,57)． ③求1997和57的所有公因数． 定理5 设a,b是任意两个不全为零的整数， (1) 若m是任意正整数，则（am,bm）=(a,b)m (2) 若 是a,b任一公因数，则 特别的 定理6 若 是任意n个不全为零的整数，则 练习：判断： 1、任意非零整数