gcd(244,117):
Step
x = qy + r
244=2·117+10 117=11·10+7
x
244 117 10 7 3 1
y
117 10 7 3 1 0
gcd = ax+by
0 1 2 3 4 5
1=-2·10+3·(117-11·10) = 3·117-35·10 1=7-2·(10-7) = -2·10+3·7 1=7-2·3
a
b
gcd = xa+yb
0 1 2
89 60 60 29 29 2
26
求逆元举例
gcd(89,60)
Step
a= qb + r 89=1·60+29 60=2·29+2
a
b
gcd = xa+yb
0 1 2
89 60 60 29 29 2
3
29=14·2+1
2
1
27
求逆元举例
gcd(89,60)
Step
x = qy + r
244=2·117+10 117=11·10+7 10=7+3 7=2·3+1
x
244 117 10 7 3
y
117 10 7 3 1
gcd = ax+by
0 1 2 3 4
1=7-2·(10-7) = -2·10+3·7 1=7-2·3
5
3=3·1+0
1
0
终止
39
求逆元举例
12
同余性质
2. 设m是一个正整数， ① ad≡bd(mod m), 如果(d, m)=1, 则a≡b(mod m) ② a≡b(mod m), k>0, 则ak≡bk(mod mk) ③ a≡b(mod m), 如果d是m的因子，则a≡ b(mod
d) 下面对①③进行证明。
13
同余性质
① 证 明 ： 若 ad≡bd(mod m), 则 m|(ad-bd), 即 m|d(a-b). 因(d, m)=1，故m|(a-b), 即a=b(mod m) ③ 证明：d是m的因子，故存在m’, 使得m=dm’. 因为a≡b(mod m), 存在k, 使得a=b+mk= b+ dm’k. 等式 两边模d, 可得a≡b(mod d).
23
求逆元举例
gcd(89,60)
Step
x = qy + r -
x
y
gcd = ax+by
0
89 60
24
求逆元举例
gcd(89,60)
Step
a= qb + r 89=1·60+29
a
b
gcd = xa+yb
0 1
89 60 60 29
25
求逆元举例
gcd(89,60)
Step
a= qb + r 89=1·60+29 60=2·29+2
0 1 2 3 4
36
求逆元举例
gcd(244,117):
Step
x = qy + r
244=2·117+10 117=11·10+7 10=7+3 7=2·3+1 3=3·1+0
x
244 117 10 7 3 1
y
117 10 7 3 1 0
gcd = ax+by
0 1 2 3 4 5
37
求逆元举例
gcd(244,117):
Step
x = qy + r
244=2·117+10 117=11·10+7 10=7+3 7=2·3+1 3=3·1+0
x
244 117 10 7 3 1
y
117 10 7 3 1 0
gcd = ax+by
0 1 2 3 4 5
1=7-2·3
终止
38
求逆元举例
gcd(244,117):
Step
a= qb + r 89=1·60+29 60=2·29+2
a
b
gcd = xa+yb
0 1 2
89 60 60 29 29 2
3
3
29=14·2+1
2=2·1+0
2
1
1
0 终止
28
求逆元举例
gcd(89,60)
Step
a= qb + r 89=1·60+29 60=2·29+2
a
b
gcd = xa+yb
0 1 2
89 60 60 29 29 2
3
3
29=14·2+1
2=2·1+0
2
1
1
0
1=29-14·2
终止
29
求逆元举例
gcd(89,60)
Step
a= qb + r 89=1·60+29
a
b
gcd = xa+yb
0 1
89 60 60 29
2
3 3
60=2·29+2
29=14·2+1 2=2·1+0
17
辗转相除法 举例
例 求gcd(184, 136)。 184=1×136+48, gcd(184,136)= gcd(136,48) 136=2×48+40, gcd(136, 48)= gcd(48, 40) 48=1×40+8, gcd(48, 40)= gcd(40, 8) 40=5×8+0, gcd(40, 8)=8 因此gcd(184, 136)= gcd(136, 40) = gcd(48, 8) = 8。
x
244 117 10 7
y
117 10 7 3
gcd = ax+by
0 1 2 3
35
求逆元举例
gcd(244,117):
Step
x = qy + r
244=2·117+10 117=11·10+7 10=7+3 7=2·3+1
x
244 117 10 7 3
y
117 10 7 3 1
gcd = ax+by
4
模运算
设n是正整数，a是整数，如果用n去除a，得商 为q，余数为r，则可以表示为： a=qn+r,0≤r<n, 用a mod n表示余数r，则r≡a mod n. 例如：令a=17, n=5,则17=3×5 +2, r =2≡17mod5
5
模运算典型实例
时钟模12的运算
6
同余
设n是正整数，a, b是整数，如果a mod n≡b mod n，则称整数a和b模n同余，记为a≡b mod n。 显然，a≡b mod n，则n|(a-b). 例如：a=17, b=-8, n=5, 因为17=3×5 +2, -8 =-2×5 +2, 则17 mod 5≡-8 mod 5，通常记为： 17≡-8 mod 5.
gcd(244,117):
Step
x = qy + r
244=2·117+10 117=11·10+7
x
244 117 10
y
117 10 7
gcd = ax+by
0 1 2
34
求逆元举例
gcd(244,117):
Step
x = qy + r
244=2·117+10 117=11·10+7 10=7+3
=2
=(11+15) mod 8=26 mod 8=2 ② [(11 mod 8)×(15 mod 8)]mod 8 =(3×7)mod 8 =21 mod 8=5 (11×15）mod 8＝165 mod 8＝5
11
同余性质
1. 若ab(mod m), cd(mod m), 则: ① ax+cy bx+dy(mod m), 其中x和y为任给整数. ② ac bd(mod m). ③ an bn(mod m), 其中 n＞0. 上面的性质容易证明，以②为例： 设a=b+q1m,c=d+q2m ac=( b+q1m)( d+q2m)=bd+(bq2+dq1+q1q2)m, 等式 两边同时模m可证。
22
求逆元举例
等式两端同时mod89得：60×(-43) ≡1mod89
故60模89的逆元为-43，为方便记为最小非负 数，因为-43≡46 mod89，故一般说60模89的逆元 为46. 如何用程序实现求逆元？ 实际上，这里的逆元通常称为乘法逆元。从后 面的学习可以看到，定义不同的运算和单位元，就 可能有不同情况下的逆元。
14
最大公因数
设a, b是整数，则a, b的所有公因数中最大的一 个公因数叫做最大公因数，通常记为gcd(a,b)。 例如12和-18的最大公因数为6，记为gcd(12,-18) =6 gcd(513,614)=？ gcd(1024,888)=？ 如果两个整数的绝对值都比较小，求它们的最 大公因数是比较容易的。如果两个数都比较大，可 以用广义欧几里德除法，也称辗转相除法。
7
同余式实例
Q: 下面哪个是真的? 3 3 (mod 17) 3 -3 (mod 17) 172 177 (mod 5) -13 13 (mod 26)