东北师范大学《离散数学》课件-第五章.pdfVIP

离散数学 第五章 第五章 数论基 第五章 数论基 础 础 第五章 数论基础 第五章 数论基础  §5.1 整除性 辗转相除  §5.2 互质 质因数分解  §5.3 合同 一次同余式  §5.4 秦九韶定理 Euler 函数  §5.5 一元高次同余式 二次剩 余 §5.1.1 整除及其性质 §5.1.1 整除及其性质 定义 5.1.1 设 a 和 b 是任意整数，若存 在整数 c ，使得 a=bc ，则说 a 是 b 的倍 数， b 是 a 的因数。或者说 a 被 b 整除 ，而 b 整除 a 。记为 b|a 。 显然，任意数整除 0 ，特别 0|0 ； 1 （- 1 ）整除任意整数。 定理 5.1.1 定理 5.1.1 对任意整数 a 和 b ， b 0 ，唯一存在一 对任意整数 a 和 b ， b 0 ，唯一存在一 对整数 q 和 r ，使得 0 ≤r ＜ |b| ， 对整数 q 和 r ，使得 0 ≤r ＜ |b| ， a=qb+r 。 q 称为 ( 不完全 ) 商数， r 称 a=qb+r 。 q 称为 ( 不完全 ) 商数， r 称 为 a 被 b 除的余数。 为 a 被 b 除的余数。 证明 ： （1 ） 当 b ＞ 0 时，存在性成立。 1 b 0 证明 ： （ ） 当 ＞ 时，存在性成立。 看函数 y=bx, x Z 。 因为 b ＞ 0 ，所以 是 x 看函数 y=bx, x Z 。 因为 b ＞ 0 ，所以 是 x 的单调递增函数，且当 x+∞ 时， +∞ ； 的单调递增函数，且当 x+∞ 时， +∞ ； 当 x -∞ 时，  -∞, 从而存在 q ，使得 x=q 当 x-∞ 时， -∞, 从而存在 q ，使得 x=q 时， y≤a ； x=q+1 时  a 。即 bq≤a ， b(q+1) 时， y≤a ； x=q+1 时  a 。即 bq≤a ， b(q+1)  a 。令 r=a-bq ，则 r ≥0 且 r b 。于是  a 。令 r=a-bq ，则 r ≥0 且 r b 。于是 ＜ b 定理 5.1.1 定理 5.1.1 （2 ） 当 b=-b’ 0 时，存在性成立。 2 b=-b’ 0 （ ） 当 时，存在性成立。 由 (1) 知，存在 q’ ， r’ ，使得 由 (1) 知，存在 q’ ， r’ ，使得 a=q’b’+r’ ， 0≤r’ b’ 。取 q=-q’ ， r=r’ ， ≤ a=q’b’+r’ ， 0 r’ b’ 。取 q=-q’ ， r=r’ ， 则得 a=-qb’+r =qb+r ， 0≤r -b 。 ≤ 则得 a=-qb’+r =qb+r ， 0 r -b 。 综合 (1) ， (2) 对任意 b (b 0) ，都有 综合 (1) ， (2