信息安全数学基础4章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整数的整除-带余除法5a的因数(约数),a称为b的倍数，能被2整除的整数称为偶数，否则称为奇数.注：每个非零整数a都有约数

1，a，称这四个数为a的平凡约数，a其他的约数称为非平凡约数。4.1整数的整除-带余除法定义4.2设a,b整数，b不为0，如果a被b除的余数为06

例3:已知：x和y是整数，13︱(9x+10y)，求证：13︱(4x+3y).

4.1整数的整除-带余除法

定义4.3设有整数的带余数除法中，每次用余数去除除数，直到余数为0停止，这种运算方法称为辗转相除法。即有或4.1整数的整除-带余除法84.1整数的整除-最大公因数例4：2,3,6互素，但不是两两互素.9定理4.5最大公因数必为正整数，且注：上述定理的(3)给出了求两个数最大公因数的方法.4.1整数的整除-最大公因数例5：求57与17的最大公因数.10定理4.64.1整数的整除-最大公因数114.1整数的整除-最大公因数对于多个整数的最大公因数，利用可以求得.例：求36,28,64的最大公因数.12定理4.74.1整数的整除-最大公因数13定理4.8

设a，b不全为0，则存在整数s,t，使得证明：对a,b作辗转相除法，并回代即得.

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)若a

b，则[a,b]=|b|。4.1整数的整除-最小公倍数15定理4.10对任意的正整数a，b，有4.1整数的整除-最小公倍数两个整数的任何公倍数一定是最小公倍数的倍数.设m，a，b是正整数，则[ma,

mb]=m[a,b].注：多个整数的公倍数化为两个数的公倍数来计算.定理4.114.1整数的整除-最小公倍数17定义4.12若整数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的整数能唯一表示成素数的乘积，即对于n>1,有n=p1p2

pm，其中pi

(1

i

m)是递增的素数，如果n还可以表示为n=q1q2

ql，其中qi

(1

i

l)是4.1整数的整除-算术基本定理递增的素数，则l=m,pi=qi

(1

i

m)

.将相同的素因子写成幂的形式，得到整数的标准分解式

定理4.17

设a,b是任意两个正整数，且4.1整数的整除-算术基本定理21例：设a=360,b=300，则4.1整数的整除-算术基本定理22第四章整除与同余整数的整除一不定方程二同余方程求解四二次剩余五整数的同余三23百钱买鸡问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡，问鸡翁母雏各几何？求解：设x,y分别表示鸡翁、鸡母的只数，则可列出方程如下：这里，方程的个数少于未知数的个数，在实数范围