信息安全数学基础4章1讲-整除课件

1、第四章 整除与同余整数的整除一不定方程二同余方程求解四二次剩余五整数的同余三1 整数环关于加法与乘法构成环：4.1 整数的整除-带余除法2 整数序： 绝对值： 正整数，负整数4.1 整数的整除-带余除法3定理4.1 设a与b是两个整数，b 0，则存在唯一的两个整数q和r，使得 4.1 整数的整除-带余除法 上述定理的等式也可写成并称q为a被b除所得的不完全商；r叫做a被b除所得的余数；上述定理的等式通常被称为带余除法。 4例1: 利用带余数除法，由a, b的值求q, r .例2: 4.1 整数的整除-带余除法5 例3: 已知：x和y是整数，13( 9x + 10y )， 求证：13( 4x +

2、 3y ). 4.1 整数的整除-带余除法 定义4.3 设有整数 的带余数除法中， 每次用余数去除除数，直到余数为0停止，这种运算方法称为辗转相除法。即有或4.1 整数的整除-带余除法8定理4.5 最大公因数必为正整数，且注：上述定理的(3)给出了求两个数最大公因数的方法.4.1 整数的整除-最大公因数例5：求57与17的最大公因数.10定理4.64.1 整数的整除-最大公因数114.1 整数的整除-最大公因数 对于多个整数的最大公因数，利用 可以求得.例：求36, 28, 64的最大公因数.12定理4.8 设a，b不全为0，则存在整数 s, t，使得证明：对a,b作辗转相除法，并回代即得.

3、4.1 整数的整除-最大公因数 14定义4.9 整数a1, a2, , ak的公共倍数称为a1, a2, , ak的公倍数。a1, a2, , ak的正公倍数中的最小的一个叫做a1, a2, , ak的最小公倍数，记为a1, a2, , ak. 下面的等成立：(1) a, 1 = |a|，a, a = |a|；(2) a, b = b, a；(3) a1, a2, , ak = |a1|, |a2| , |ak|；(4) 若ab，则a, b = |b|。4.1 整数的整除-最小公倍数15注：多个整数的公倍数化为两个数的公倍数来计算.定理4.114.1 整数的整除-最小公倍数17定义4.12 若

4、整数a 1，并且它的因数只有1和 a，称a是素数（或质数）；否则称a为合数. 定理4.13 设a是大于1的整数，则（1）除1外， a的最小正因数q是质数；（2）若a是合数，则a的最小正因数4.1 整数的整除-素数与合数18注：在推论中，若p不是质数，则结论不能成立.4.1 整数的整除-素数与合数19定理4.16 算术基本定理任一大于1的整数能唯一表示成素数的乘积，即对于n1, 有n = p1p2pm ，其中pi (1 i m)是递增的素数，如果n还可以表示为n= q1q2ql，其中qi (1 i l)是4.1 整数的整除-算术基本定理递增的素数，则 l=m, pi = qi (1 i m) .

5、 将相同的素因子写成幂的形式，得到整数的标准分解式 定理4.17 设a,b是任意两个正整数，且4.1 整数的整除-算术基本定理21例：设a=360, b=300，则4.1 整数的整除-算术基本定理22百钱买鸡问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡，问鸡翁母雏各几何？求解：设x, y分别表示鸡翁、鸡母的只数，则可列出方程如下：这里，方程的个数少于未知数的个数，在实数范围内，方程的解有无穷多个。而我们所关心的是其有无整数或正整数解，这种方程称为不定方程。4.2 不定方程- 二元一次不定方程24注：该方法对一次项系数较小的方程比较实用。4.2 不定方程-二元一次不定方程25

6、例2： 求下列方程通解的形式：4.2 不定方程-二元一次不定方程注：上述方程求解的关键在于求一个特解.27定理4.19 有整数解 4.2 不定方程-二元一次不定方程例 求 的一切整数解。解: 321111312，111129+3， 9=33+0方程的一个整数解是 原方程的整数解为 28定理4.20 方程 4.2 不定方程-多元一次不定方程 多元方程解法： 若d不能整除N，则原方程无整数解； 否则，继续下面的步骤.29(2) 构造如下的n-1个方程(3) 求出每个方程的所有整数解 (含参数ti ), 再逐步代入上面的方程中，消去所有的ti，从而得到原方程的所有整数解。4.2 不定方程-多元一次不

7、定方程30例 求不定方程 x 2y 3z = 7 的所有整数解。（1）的解为（2）的解为把(4)代入(3),消去t,得4.2 不定方程-多元一次不定方程31 习题习题2: 已知： 782 + 8161能被57整除，求证：783 +8163也能被57整除。习题3: 写出51480的标准分解式。习题4： 求 的一切整数解。习题1: 若n是正整数，则 32习题1: 若n是正整数，则 习题33证明：783 + 8163 = 7 ( 782 + 8161 )7 8161 + 8163= 7 ( 782 + 8161 ) + 8161 57782 + 8161和57都能被57整除原式得证。 习题习题2: 已知： 782 + 8161能被57整除，求证：783