第一节 整除与带余数除法
定理1 下面的结论成立： (1) ab，bc ac；（传递性） (2) ma，mb m(a±b) (3) mai，i = 1, 2, , n ma1q1 a2q2 anqn， 此处qi∈Z（i = 1, 2, , n）。
第一节 整除与带余数除法
注： ① ab ab； ② ba bcac，此处c是任意的非零整数； ③ ba，a 0 |b| |a|； ba且|a| < |b| a = 0。
密码学数学
整数性质
教学目的和要求 （1）深刻理解整除、最大公因数、最小公
倍数、质数的概念，正确理解带余数除法 的意义及作用。 （2）掌握并能直接运用辗转相除法求最大 公因数。
第一节 整除与带余数除法
定义1 设a，b是整数，b 0，如果存在 整数q，使得
a = bq
成立，则称b整除a或a被b整除，此时a是 b的倍数，b是a的因数（约数或除数）， 并且记作：ba；如果不存在整数q使得 a = bq成立，则称b不能整除a或a不被b整 除，记作：b a。 |
此题可以推广为：
推论 (a1, a2, , an) = 1的充要条件是：存在 整数x1, x2, , xn，使得 a1x1 a2x2 anxn = 1。
欧几里德公式
gcd(a,b) gcd(b, a modb)
第四节 模运算
令整数 a及, b n ， 0若 a b (kkn为任一整
Pi
pi
欧拉定理 对于任何互素的两个整数a和n，有
a(n) 1modn
当n为素数时，欧拉定理相当于费马定理
求7803的后三位数字 求11803的后三位数字
思考
1、如果今天是星期一，问从今天起再过
101010 天是星期几？
第七节 本原元
对于任何互素的两个整数a和n，在方程 这一am方程1m（od中因n ，为至少有是(一n其) 个中正的整一数个m解满）足，
那么，最小的正整数解m为模n下a的阶。
如果a的阶m= ，称a为(nn的) 本原元。
第八节 中国剩余定理
《孙子算经》下卷第26题所提出的问题如下: “今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二。问物几何？” “答曰：二十三。”
相当于求同余方程组 n 2 (mod 3) n 3(mod 5) n 2 (mod 7)
任何大于1的整数a都可以分解成素数幂
之积，且唯一。
a
p a1 1
p a2 2
p at t
其中，pi为素数，ai为正整数。
第三节 最大公因数
定义1 设a1, a2, , an是n（n≥2）个整数， 若整数d是它们之中每一个的因数，则d就 叫做a1, a2, , an的一个公因数；其中最大 的一个公因数叫做a1, a2, , an的最大公因 数。记为(a1, a2, , an)。
第五节 模逆元
模逆元的计算可以通过扩展欧几里德算 法实现。
第六节 费马欧拉定理
费马定理 如果p是素数，且p不能被a整除，那么
a p1 1mod p
欧拉函数 (m)
表示比m小，且与m互素的正整数的个数
欧拉函数性质：
当m是素数时， =m-1 当m=pq，且p、q（(mp) ≠q）均为素数时，
，
数)，则称 a在maobd nm下o与db同n余，记为
。
性质：
(a b)
modn
((a
modn)
(b
modn))modn
(a b) modn ((a modn) (bmodn))modn
(a b)modn ((a modn)(bmodn))modn
例（7+9）mod11 （7×9）mod11计算 97 mod 13 证来自 13200-1 是51的倍数
例 说明 225 是1 否被641整除。
解 ： 22 4，24 16，28 256，216 154，232
1 (mod 641)。
因此 225 1 0 (mod 641)，
即641225 1
例 求(25733 46)26 mod 50 解： (25733 46)26 (733 4)26 = [7(72)16 4]26 [7( 1)16 4]26 = (7 4)26 326 = 3(35)5 3(7)5 = 37(72)2 21 29 (mod 50)， 即所求的余数是29。
第一节 整除与带余数除法
定理2(带余数除法)
设a与b是两个整数，b >0，则存在唯一 的两个整数q和r，使得
a = bq r，0 r < b。
(1)
此外，ba的充要条件是r=0
第二节 素数
如果正整数P >1只能被1和它本身整除， 则该数为素数（也叫质数）
100以内的素数有25个，分别是2、3、5、 7、11、13、17、19、23、29、31、37、41、 43、47、53、59、61、67、71、73、79、 83、89和97。
由于每个非零整数的因数的个数是有
限的，所以最大公因数是存在的，且是正
整数。
最大公因数
若(a1, a2, , an) = 1， 则称a1, a2, , an是互质的； 若(ai, a j) = 1，1 i, j n，i j， 则称a1, a2, , an是两两互质的。 显然，a1, a2, , an两两互质可以推出(a1, a2,
=
=(p-1)(q-1)
(m) ( p) (q)
计算欧拉函数的公式 1. 若一个数m可以写成m=
p e1 1
p e2 2
p et t
( 为pi 素数)，则
t
(m) pi ei 1 ( pi 1)
i 1
2.对任一正整数m，若其可写成，
p e1 1
p e2 2
则 p et t
(m) m (1 1 )
, an) = 1，反之则不然，例如(2, 6, 15) = 1， 但(2, 6) = 2。
最大公因数
由上我们容易得到：
定理 （裴蜀（Bé zout,1730-1783）恒等式） 设a，b是任意两个不全为零的整数，则 存在s，t∈Z，使得
as bt = (a, b)
最大公因数
推论 (a, b)＝1的充要条件是：存在s，t∈Z， 使得 as bt = 1。