Bài tập có lời giải
An tồn và bảo mật thơng tin
Phần 1: Phép tốn số học theo Modulo
Câu 1: Tính
(11 * 19 + 1017) mod 7
= ((11 * 19 mod 7) + (1017 mod 7)) mod 7
= ((11 mod 7 * 19 mod 7) mod 7 + (10 mod 7)17) mod 7
= (( 4
*
5
) mod 7 + (3 mod 7)17) mod 7
= (6 + (((98) mod 7) * 3mod 7) mod 7)) mod 7
= (6 + ((28 mod 7) * 3 mod 7)) mod 7
= (6 + ((4*3) mod7)) mod 7
= (6 + 5) mod 7
= 11 mod 7
=4

Phần 2: Cộng và nhân theo Modulo
Bài tập 1: Cho a=87, b=94 thực hiện phép cộng (a+b) mod 7
Bài tập 2: Cho a=354, b=173 thực hiện phép cộng (a+b) mod 8
Bài tập 3: Cho a=87, b=6 thực hiện phép nhân (axb) mod 7
Bài tập 4: Cho a=354, b=5 thực hiện phép nhân (axb) mod 8

Bài Làm:
Bài tập 1: Cho a=87, b=94 thực hiện phép cộng (a+b) mod 7
• Chuyển đổi a=87, b=94 từ hệ cơ số 10 sang cơ số 7
o a = 153
o b = 163
• Thực hiện phép cộng:
o (3+3) mod 7 = 6 mod 7 được 0 dư 6

o (5+6) mod 7 = 11 mod 7 được 1 dư 4
o (1+1+1(nhớ)) mod 7 = 3 mod 7 được 0 dư 3
• Kết quả (a + b) mod 7 = 346
1


Bài tập 2: Cho a=354, b=173 thực hiện phép cộng (a+b) mod 8
• Chuyển đổi a=354, b=173 từ hệ cơ số 10 sang cơ số 8
o a = 542
o b = 255
• Thực hiện phép cộng:
o (2+5) mod 8 = 7 mod 8 được 0 dư 7
o (4+5) mod 8 = 9 mod 8 được 1 dư 1
o (5+2+1(nhớ)) mod 8 = 8 mod 8 được 1 dư 0
• Kết quả (a + b) mod 8 = 1017
Bài tập 3: Cho a=87, b=6 thực hiện phép nhân (axb) mod 7
• Chuyển đổi a=87, b=6 từ hệ cơ số 10 sang cơ số 7
o a = 153
o b=6
• Thực hiện phép nhân:
o (3x6) mod 7 = 18 mod 7 được 2 dư 4
o (5x6+2(nhớ)) mod 7 = 32 mod 7 được 4 dư 4
o (1x6+4(nhớ)) mod 7 = 10 mod 7 được 1 dư 4
• Kết quả (a x b) mod 7 = 1344
Bài tập 4: Cho a=354, b=5 thực hiện phép nhân (axb) mod 8
• Chuyển đổi a=354, b=5 từ hệ cơ số 10 sang cơ số 8
o a = 542
o b=5
• Thực hiện phép nhân:
o (2x5) mod 8 = 10 mod 8 được 1 dư 2

o (4x5+1(nhớ)) mod 8 = 21 mod 8 được 2 dư 5
o (5x5+2(nhớ)) mod 8 = 27 mod 8 được 3 dư 3
• Kết quả (a x b) mod 8 = 3352

2


Phần 3:
Thuật tốn Euclide tính ước chung nhỏ nhất GCD
Bài tập 1: Tìm GCD(973, 301).
Bài tập 2: Tìm GCD(1970, 1066).
Bài tập 3: Tìm GCD(4864, 3458).
Bài tập 4: Tìm GCD(42823, 6409).
Bài tập 5: Tìm GCD(91470, 51066).

Bài giải
Bài tập 1: Tìm GCD(973, 301).
973 = 3*301 + 70
301 = 4*70 + 21
70 = 3*21 + 7
21 = 3*7 + 0

GCD(973, 301) = GCD(301, 70)
GCD(301, 70) = GCD(70, 21)
GCD(70, 21) = GCD(21, 7)
GCD(21, 7) = GCD(7, 0) = 7

Vậy GCD(973, 301) = 7
Bài tập 2: Tìm GCD(1970, 1066).
1970= 1*1066 + 904

1066= 1*904 + 162
904 = 5*162 + 94
162 = 1*94 + 68
94 = 1*68 + 26
68 = 2*26 + 16
26 = 1*16 + 10
16 = 1*10 + 6
10 = 1*6 + 4
6 = 1*4 + 2
4 = 2*2 + 0

GCD(1970, 1066) = GCD(1066, 904)
GCD(1066, 904) = GCD(904, 162)
GCD(904, 162) = GCD(162, 94)
GCD(162, 94) = GCD(94, 68)
GCD(94, 68) = GCD(68, 26)
GCD(68, 26) = GCD(26, 16)
GCD(26, 16) = GCD(16, 10)
GCD(16, 10) = GCD(10, 6)
GCD(10, 6) = GCD(6, 4)
GCD(6, 4) = GCD(4, 2)
GCD(4, 2) = GCD(2, 0) = 2

Vậy GCD(1970, 1066) = 2

3


Bài tập 3: Tìm GCD(4864, 3458)
4864= 1*3458+ 1406

3458= 2*1406+ 646
1406= 2*646+ 114
646= 5*114+ 76
114= 1*76+ 38
76= 2*38+ 0
Vậy GCD(4864, 3458) = 38

GCD(4864, 3458) = GCD(3458, 1406)
GCD(3458, 1406) = GCD(1406, 646)
GCD(1406, 646) = GCD(646, 114)
GCD(646, 114) = GCD(114, 76)
GCD(114, 76) = GCD(76, 38)
GCD(76, 38) = GCD(38, 0) = 38

Bài tập 4: Tìm GCD(42823, 6409).
42823= 6*6409+ 4369
6409= 1*4369+ 2040
4369= 2*2040+ 289
2040= 7*289+ 17
289= 17*17+ 0
Vậy GCD(42823, 6409) = 17

GCD(42823, 6409) = GCD(6409, 4369)
GCD(6409, 4369) = GCD(4369, 2040)
GCD(4369, 2040) = GCD(2040, 289)
GCD(2040, 289) = GCD(289, 17)
GCD(289, 17) = GCD(17, 0) = 17

Bài tập 5: Tìm GCD(91470, 51066).
91470= 1*51066+ 40404

51066= 1*40404+ 10662
40404= 3*10662+ 8418
10662= 1*8418+ 2244
8418= 3*2244+ 1686
2244= 1*1686+ 558
1686= 3*558+ 12
558= 46*12 + 6
12 = 2*6 + 0
Vậy GCD(91470, 51066) = 6

GCD(91470, 51066) = GCD(51066, 40404)
GCD(51066, 40404) = GCD(40404, 10662)
GCD(40404, 10662) = GCD(10662, 8418)
GCD(10662, 8418) = GCD(8418, 2244)
GCD(8418, 2244) = GCD(2244, 1686)
GCD(2244, 558) = GCD(1686, 558)
GCD(1686, 558) = GCD(558, 12)
GCD(558, 12) = GCD(12, 6)
GCD(12, 6) = GCD(6, 0) = 6

4


Phần 4:
Thuật tốn Euclide mở rộng tính GCD
và x, y thoả mãn ax + by = GCD(a,b)
Bài tập 1: Cho a=973, b=301. Tìm x,y và GCD(a,b) thoản mãn ax + by = GCD(a,b)
Bài tập 2: Cho a=1970, b=1066. Tìm x,y và GCD(a,b) thoản mãn ax + by =
GCD(a,b)
Bài tập 3: Cho a=42823, b=6409. Tìm x,y và GCD(a,b) thoản mãn ax + by =

GCD(a,b)
Bài tập 4: Cho a=91470, b=51066. Tìm x,y và GCD(a,b) thoản mãn ax + by =
GCD(a,b)

Bài làm:
Bài tập 1: Cho a=973, b=301. Tìm x,y và GCD(a,b) thoản mãn ax + by = GCD(a,b)
Bước
0
1
2
3
4

q

r
3
4
3
3

70
21
7
0

x
1
-4
13

-43

y
-3
13
-42
139

a
973
301
70
21
7

Bước 1:
• a = 973 chia b = 301 được q=3, r=70
• x = x2 – q*x1 = 1-3*0 = 1
• y = y2 – q*y1 = 0-3*1=-3
• a = b = 301, b = r = 70
• x2 = x1 = 0, x1 = x = 1
• y2 = y1 = 1, y1 = y = -3
Bước 2:
• a = 301 chia b = 70 được q=4, r=21
• x = x2 – q*x1 = 0-4*1 = -4
• y = y2 – q*y1 = 1-4*-3=13
• a = b = 70, b = r = 21
• x2 = x1 = 1, x1 = x = -4
• y2 = y1 = -3, y1 = y = 13
5


b
301
70
21
7
0

x2
1
0
1
-4
13

x1

y2

y1

0
1
-4
13
-43

0
1
-3

13
-42

1
-3
13
-42
139


Bước 3:
• a = 70 chia b = 21 được q=3, r=7
• x = x2 – q*x1 = 1-3*-4 = 13
• y = y2 – q*y1 = -3-3*13=-42
• a = b = 21, b = r = 7
• x2 = x1 = -4, x1 = x = 13
• y2 = y1 = 13, y1 = y = -42
Bước 4:
• a = 21 chia b = 7 được q=3, r=0
• x = x2 – q*x1 = -4-3*13 = -43
• y = y2 – q*y1 = 13-3*-42=139
• a = b = 7, b = r = 0
• x2 = x1 = 13, x1 = x = -43
• y2 = y1 = -42, y1 = y = -139
Do b = 0, Thuật toán kết thúc: a = 7 = d =gcd(973,301); x = x2 = 13, y = y2 = -42
Bài tập 2: Cho
GCD(a,b)
Bước
q
0

1
1
2
1
3
5
4
1
5
1
6
2
7
1
8
1
9
1
10
1
11
2

a=1970, b=1066. Tìm x,y và GCD(a,b) thoản mãn ax + by =
r
904
162
94
68
26

16
10
6
4
2
0

x
1
-1
6
-7
13
-33
46
-79
125
-204
533

y
-1
2
-11
13
-24
61
-85
146
-231

377
-985

a
b
1970 1066
1066 904
904 162
162
94
94
68
68
26
26
16
16
10
10
6
6
4
4
2
2
0

Bước 1:
• a = 1970 chia b = 1066 được q=1, r=904
• x = x2 – q*x1 = 1-1*0 = 1

• y = y2 – q*y1 = 0-1*1=-1
• a = b = 1066, b = r = 904
6

x2

x1

y2

y1

1
0
1
-1
6
-7
13
-33
46
-79
125
-204

0
1
-1
6
-7

13
-33
46
-79
125
-204
533

0
1
-1
2
-11
13
-24
61
-85
146
-231
377

1
-1
2
-11
13
-24
61
-85
146

-231
377
-985


• x2 = x1 = 0, x1 = x = 1
• y2 = y1 = 1, y1 = y = -1
Bước 2:
• a = 1066 chia b = 904 được q=1, r=162
• x = x2 – q*x1 = 0-1*1 = -1
• y = y2 – q*y1 = 1-1*-1=2
• a = b = 904, b = r = 162
• x2 = x1 = 1, x1 = x = -1
• y2 = y1 = -1, y1 = y = 2
Bước 3,4,5,6,7,8,9,10,11 tương tự ta có:
• a chia b được q dư r
• x = x2 – q*x1
• y = y2 – q*y1
• a = b, b = r
• x2 = x1, x1 = x
• y2 = y1, y1 = y
Do b = 0, Thuật toán kết thúc: a = 2 = d =gcd(1970, 1066); x = x2 = -204, y = y2 =
377
Bài tập 3: Cho a=42823, b=6409. Tìm x,y và GCD(a,b) thoản mãn ax + by =
GCD(a,b)
Bước
0
1
2
3

4
5

q

r
6
1
2
7
17

4369
2040
289
17
0

x
1
-1
3
-22
377

y
-6
7
-20
147

-2519

a

b

42823

6409

6409
4369
2040
289
17

4369
2040
289
17
0

Bước 1:
• a = 42823 chia b = 6409 được q=6, r=4369
• x = x2 – q*x1 = 1-6*0 = 1
• y = y2 – q*y1 = 0-6*1=-6
• a = b = 6409, b = r = 4369
• x2 = x1 = 0, x1 = x = 1
• y2 = y1 = 1, y1 = y = -6
Bước 2:

• a = 6409 chia b = 4369 được q=1, r=2040
• x = x2 – q*x1 = 0-1*1 = -1
7

x2
1
0
1
-1
3
-22

x1
0
1
-1
3
-22
377

y2
0
1
-6
7
-20
147

y1
1

-6
7
-20
147
-2519


• y = y2 – q*y1 = 1-1*-6=7
• a = b = 4369, b = r = 2040
• x2 = x1 = 1, x1 = x = -1
• y2 = y1 = -6, y1 = y = 7
Bước 3:
• a = 4369 chia b = 2040 được q=2, r=289
• x = x2 – q*x1 = 1-2*-1 = 3
• y = y2 – q*y1 = -6-2*7=-20
• a = b = 2040, b = r = 289
• x2 = x1 = -1, x1 = x = 3
• y2 = y1 = 7, y1 = y = -20
Bước 4:
• a = 2040 chia b = 289 được q=7, r=17
• x = x2 – q*x1 = -1-7*3 = -22
• y = y2 – q*y1 = 7-7*-20=147
• a = b = 289, b = r = 17
• x2 = x1 = 3, x1 = x = -22
• y2 = y1 = -20, y1 = y = 147
Bước 5:
• a = 289 chia b = 17 được q=17, r=0
• x = x2 – q*x1 = 3-17*-22 = 377
• y = y2 – q*y1 = -20-17*147=-2519
• a = b = 17, b = r = 0

• x2 = x1 = -22, x1 = x = 377
• y2 = y1 = 147, y1 = y = -2519
Do b = 0, Thuật toán kết thúc: a = 17 = d =gcd(42823, 6409); x = x2 = -22, y = y2 =
147

8


Bài tập 4: Cho a=91470, b=51066. Tìm x,y và GCD(a,b) thoản mãn ax + by =
GCD(a,b)
Bước q
r
x
y
0
1
1 40404
1
-1
2
1 10662
-1
2
3
3 8418
4
-7
4
1 2244
-5

9
5
3 1686
19
-34
6
1
558
-24
43
7
3
12
91
-163
8
46
6 -4210
7541
9
2
0 8511 -15245

a
b
x2
x1
y2
y1
91470 51066

1
0
0
1
51066 40404
0
1
1
-1
40404 10662
1
-1
-1
2
10662 8418
-1
4
2
-7
8418 2244
4
-5
-7
9
2244 1686
-5
19
9
-34
1686

558
19
-24
-34
43
558
12
-24
91
43
-163
12
6
91 -4210 -163
7541
6
0 -4210 8511 7541 -15245

Bước 1:
• a = 91470 chia b = 51066 được q=1, r=40404
• x = x2 – q*x1 = 1-1*0 = 1
• y = y2 – q*y1 = 0-1*1=-1
• a = b = 51066, b = r = 40404
• x2 = x1 = 0, x1 = x = 1
• y2 = y1 = 1, y1 = y = -1
Bước 2:
• a = 51066 chia b = 40404 được q=1, r=10662
• x = x2 – q*x1 = 0-1*1 = -1
• y = y2 – q*y1 = 1-1*-1=2
• a = b = 40404, b = r = 10662

• x2 = x1 = 1, x1 = x = -1
• y2 = y1 = -1, y1 = y = 2
Bước 3,4,5,6,7,8,9,10,11 tương tự ta có:
• a chia b được q dư r
• x = x2 – q*x1
• y = y2 – q*y1
• a = b, b = r
• x2 = x1, x1 = x
• y2 = y1, y1 = y
Do b = 0, Thuật toán kết thúc: a = 6 = d =gcd(91470, 51066); x = x2 = -4210, y =
y2 = 7541
9


Phần 5:
Dùng thuật tốn Euclide mở rộng tính nghịch đảo vành Zn
Bài tập 1: Tính r1-1 mod r0 với r0=101, r1=25
Bài tập 2: Tính r1-1 mod r0 với r0=11, r1=60
Bài tập 3: Tính r1-1 mod r0 với r0=1024, r1=173
Bài tập 4: Tính r1-1 mod r0 với r0=323, r1=299
Bài tập 5: Tính r1-1 mod r0 với r0=460, r1=3
Bài Làm:
Bài tập 1: Tính r1-1 mod r0 với r0=101, r1=25
Bước
ri
qi+1
ri+1
0
101
4

25
1
25
25
1
2

ri+2

si
1
0

ti
1
0
1

0
1
-4

❖ Bước 0: ri = r0 = 101, ri+1= r1 = 25, r0 chia r1 được q1 = 4, dư r2=1, s0=1, t0=0
❖ Bước 1: r1 = 25, r2 = 1, r1 chia r2 được q2 = 25, dư r3=0, s1=0, t1=1
❖ Bước 2: s2=1, t2=-4
Ta Thấy 101 * 1 + 25 * -4 = GCD(101,25) = 1 => s=1, t=-4
Vậy 25-1 mod 101 = (-4) mod 101 = (-4 + 101) = 97
Bài tập 2: Tính r1-1 mod r0 với r0=11, r1=60
Bước
ri

qi+1
ri+1
ri+2
si
0
11
0
60
11
1
1
60
5
11
5
0
2
11
2
5
1
1
3
5
5
1
0
-5
4
11

❖
❖
❖
❖
❖

ti
0
1
0
1
-2

Bước 0: ri = r0 = 11, ri+1= r1 = 60, r0 chia r1 được q1 = 0, dư r2=11, s0=1, t0=0
Bước 1: r1 = 60, r2 = 11, r1 chia r2 được q2 = 5, dư r3=5, s1=0, t1=1
Bước 2: r2 = 11, r3 = 5, r2 chia r3 được q3 = 2, dư r4=5, s2=1, t2=0
Bước 3: r3 = 60, r4 = 11, r3 chia r4 được q4 = 5, dư r5=5, s3=-5, t3=1
Bước 4: s4=11, t4=-2

Ta Thấy 11 * 11 + 60 * -2 = GCD(11,60) = 1 => s=11, t=-2
Vậy 60-1 mod 11 = (-2) mod 11 = -2 + 11 = 9
10


Bài tập 3: Tính r1-1 mod r0 với r0=1024, r1=173
Bước
ri
qi+1
ri+1
ri+2

0
1024
5
173
159
1
173
1
159
14
2
159
11
14
5
3
14
2
5
4
4
5
1
4
1
5
4
4
1
0

6
❖
❖
❖
❖
❖
❖
❖

si
1
0
1
-1
12
-25
37

ti
0
1
-5
6
-71
148
-219

Bước 0: ri = r0 = 1024, ri+1= r1 = 173, r0 chia r1 được q1 = 5, dư r2=159, s0=1, t0=0
Bước 1: r1 = 173, r2 = 159, r1 chia r2 được q2 = 1, dư r3=14, s1=0, t1=1
Bước 2: r2 = 159, r3 = 14, r2 chia r3 được q3 = 11, dư r4=5, s2=1, t2=-5

Bước 3: r3 = 14, r4 = 5, r3 chia r4 được q4 = 2, dư r5=4, s3=-1, t3=6
Bước 4: r4 = 5, r5 = 4, r4 chia r5 được q5 = 1, dư r6=1, s4=12, t4=-71
Bước 5: r5 = 4, r6 = 1, r5 chia r6 được q6 = 4, dư r7=0, s5=-25, t5=148
Bước 6: s5=37, t5=-219

Ta Thấy 1024 * 37 + 173 * -219 = GCD(1024,173) = 1 => s=37, t=-219
Vậy 173-1 mod 1024 = (-219) mod 1024 = -219 + 1024 = 805
Bài tập 4: Tính r1-1 mod r0 với r0=323, r1=299
Bước
ri
qi+1
ri+1
0
323
1
299
1
299
12
24
2
24
2
11
3
11
5
2
4
2

2
1
5
❖
❖
❖
❖
❖
❖

ri+2
24
11
2
1
0

si

ti

1
0
1
-12
25
-137

0
1

-1
13
-27
148

Bước 0: ri = r0 = 323, ri+1= r1 = 299, r0 chia r1 được q1 = 1, dư r2=24, s0=1, t0=0
Bước 1: r1 = 299, r2 = 24, r1 chia r2 được q2 = 12, dư r3=11, s1=0, t1=1
Bước 2: r2 = 24, r3 = 11, r2 chia r3 được q3 = 2, dư r4=2, s2=1, t2=-1
Bước 3: r3 = 11, r4 = 2, r3 chia r4 được q4 = 5, dư r5=1, s3=-12, t3=13
Bước 4: r4 = 2, r5 = 1, r4 chia r5 được q5 = 2, dư r6=0, s4=25, t4=-27
Bước 5: s5=-137, t5=148

Ta Thấy 323 * -137 + 299 * 148 = GCD(323,299) = 1 => s=-137, t=148
11


Bài tập 5: Tính r1-1 mod r0 với r0=460, r1=3
Bước
ri
qi+1
ri+1
0
460
153
3
1
3
3
1
2


ri+2

si
1
0

ti
1
0
1

0
1
-153

❖ Bước 0: ri = r0 = 460, ri+1= r1 = 3, r0 chia r1 được q1 = 153, dư r2=1, s0=1, t0=0
❖ Bước 1: r1 = 3, r2 = 1, r1 chia r2 được q2 = 3, dư r3=0, s1=0, t1=1
❖ Bước 2: s2=1, t2=-153
Ta Thấy 460 * 1 + 3 * -153 = GCD(460,3) = 1 => s=1, t=-153

12


Phần 6:
Bình phương và nhân xk mod n
Bài tập 1: Tính xk mod n, với x = 7, k =560, n=561
Bài tập 2: Tính 1435 mod 11
Bài tập 3: Tính 31130 mod 23
Bài tập 1: Tính 7560 mod 561

• x = 7, k =560, n=561
• k = 560 = 10001100002
• p = 1, Ta có bảng:
b[i]
p=p*p
p=p(mod 561) p = p * x p =p(mod 561)
2
1
1 =1
1
7
7
2
0
7 =49
49
49
2
0
49 =2401
157
157
2
0
157 =24649
526
526
2
1
526 =276676

103
721
160
2
1
160 =25600
355
2485
241
2
0
241 =58081
298
298
2
0
298 =88804
166
166
2
0
166 =27556
67
67
2
0
67 =4489
1
1
Vậy 7560 mod 561 = 1

Bài tập 2: Tính 1435 mod 11
• x = 14, k =35, n=11
• k = 35 = 1000112
• p = 1, Ta có bảng:
b[i] p=p*p p=p(mod 11) p = p * x p = (mod 11)
1
1
1
14
3
0
9
9
9
0
81
4
4
0
16
5
5
1
25
3
42
9
1
81
4

56
1
35
Vậy 14 mod 11 = 1
13


Bài tập 3: Tính 31130 mod 23
• x = 31, k =130, n=23
• k = 130 = 100000102
• p = 1, Ta có bảng:
b[i] p=p*p p=p(mod 23) p = p * x p = (mod 23)
1
1
1
31
8
0
64
18
18
0
324
2
2
0
4
4
4
0

16
16
16
0
256
3
3
1
9
9
279
3
0
9
9
9
Vậy 31130 mod 23 = 9
Bài tập 4: Tính 71130 mod 23
• x = 71, k =130, n=23
• k = 130 = 100000102
• p = 1, Ta có bảng:
b[i] p=p*p p=p(mod n) p = p * x p = (mod n)
1
1
1
71
2
0
4
4

4
0
16
16
16
0
256
3
3
0
9
9
9
0
81
12
12
1
144
6
426
12
0
144
6
6
Vậy 71130 mod 23 = 6

14



Phần 7:
Định lý Ferma nhỏ - Phi Ơle
Dùng định lý Ferma và định lý ơle tính các biểu thức sau:
Bài 1: 616 mod 17
Bài 2: 1516 mod 17
Bài 3: 95100 mod 101
Bài 4: 74 mod 10
Bài 5: 95 mod 10
Bài 6: 1012 mod 21
Bài 7: 9190 mod 100
Bài làm:
Bài 1: 616 mod 17
Ta thấy 616 = 617-1 và 17 là số nguyên tố, GCD(6,17) = 1
Nên ta có:
616 mod 17 = 617-1 mod 17 ≡ 1 mod 17 = 1 (Theo định lý ferma nhỏ)
=>Vậy 616 mod 17 = 1
Bài 2: 1516 mod 17
Ta thấy 1516 = 1517-1 và 17 là số nguyên tố, GCD(15,17) = 1
Nên ta có:
1516 mod 17 = 1517-1 mod 17 ≡ 1 mod 17 = 1 (Theo định lý ferma nhỏ)
=>Vậy 1516 mod 17 = 1
Bài 3: 95100 mod 101
Ta thấy 95100 = 95101-1 và 101 là số nguyên tố, GCD(95,101) = 1
Nên ta có:
95100 mod 101 = 95101-1 mod 101 ≡ 1 mod 101 = 1 (Theo định lý ferma nhỏ)
=>Vậy 95100 mod 101 = 1
Bài 4: 74 mod 10
Ta thấy Ф(10) = Ф(2*5) = Ф(2)* Ф(5) (TC2) = (2-1)*(5-1) (TC1)= 4
=> 74 mod 10 = 7Ф(10) mod 10 ≡ 1 mod 10 (Định lý ơle) = 1 (mod 10)

=> Vậy 74 mod 10 = 1 (mod 10)
Bài 5: 95 mod 10
Ta có:
95 mod 10 = (94 *9) mod 10 = (94 mod 10 * 9 mod 10) mod 10
15


Do: Ф(10) = Ф(2*5) = Ф(2)* Ф(5) (TC2) = (2-1)*(5-1) (TC1)= 4
=> 95 mod 10 = (94 *9) mod 10 = (94 mod 10 * 9 mod 10) mod 10
= (9Ф(10) mod 10 * 9 mod 10) mod 10
=(
1
*
9 ) mod 10
=9
=> Vậy 95 mod 10 = 9
Bài 6: 1012 mod 21
Ta thấy Ф(21) = Ф(3*7) = Ф(3)* Ф(7) (TC2) = (3-1)*(7-1) (TC1)= 2*6 = 12
=> 1012 mod 21 = 10Ф(21) mod 21 ≡ 1 mod 21 (Định lý ơle) = 1 (mod 21)
=> Vậy 1012 mod 21 = 1
Bài 7: 9190 mod 100
Do Ф(100) = 40
=> 9190 mod 100 = (9180) * 9110 mod 100 = 9110 mod 100 = (912)5 mod 100 = 1

16


Phần 8:
Định lý phần dư Trung Hoa
Sử dụng định lý phần dư Trung Hoa tính giá trị biểu thức sau:

Bài 1: 2530 mod (7*8)
Bài 2: 70254 mod (11*13)
Bài 3: 60-1 mod (11*13)
Bài 4: ((21100 + 33-1) * 4551) mod (7*9*11)
Bài 5: ((19125 + 2551) * 4721/37) mod (9*11*13)
Bài làm:
Bài 1: 2530 mod (7*8)
A = 2530, M = 7*8
➢ Bước 1: M = 7*8 = m1 * m2 (m1 = 7, m2 = 8)
➢ Bước 2: Tính:
o M1 = M/m1 = (7*8)/7 = 8
o M1 = M/m1 = (7*8)/8 = 7
➢ Bước 3:
o a1 = A mod m1 = 2530 mod 7 = 3
o a2 = A mod m2 = 2530 mod 8 = 2
➢ Bước 4:
o c1 = M1 * (M1-1 mod m1) = 8*(8-1 mod 7) = 8*(1-1 mod 7) = 8
o c2 = M2 * (M2-1 mod m2) = 7*(7-1 mod 8) = 7*7 = 49
➢ Bước 5: A = (a1*c1 + a2*c2) mod (7*8) = (3*8 + 2*49) mod 56 = 10 (mod 56)
Vậy 2530 mod (7*8) = 10
Bài 2: 70254 mod (11*13)
➢ Bước 1: A = 70254, M = (11*13) = 143, m1=11, m2=13
➢ Bước 2:
o M1 = M/m1 = (11*13) /11=13
o M2 = M/m1 = (11*13) /13=11
➢ Bước 3:
o a1 = A mod m1 = 70254 mod 11 = 8
o a2 = A mod m2 = 70254 mod 13 = 2
➢ Bước 4:
o c1 = M1 * (M1-1 mod m1) = 13*(13-1 mod 11) = 13*(2-1 mod 11) = 13*6

= 78
o c2 = M2 * (M2-1 mod m2) = 11*(11-1 mod 13) = 11*6 = 66
17


➢ Bước 5: A = (a1*c1 + a2*c2) mod 143 = (8*78+ 2*66) mod 143 = 41 (mod
143)
Vậy 70254 mod (11*13) = 41
Bài 3: 60-1 mod (11*13)
➢ Bước 1: A = 60-1, M = (11*13)=143, m1=11, m2=13
➢ Bước 2:
o M1 = M/m1 = 143/11 = 13
o M2 = M/m2 = 143/13 = 11
➢ Bước 3:
o a1= A mod m1 = 60-1 mod 11 = 5-1 mod 11 = 9
o a2= A mod m2 = 60-1 mod 13 = 8-1 mod 13 = 5
➢ Bước 4:
o c1 = M1 * (M1-1 mod m1) = 13*(13-1 mod 11) = 13*(2-1 mod 11) = 13*6
= 78
o c2 = M2 * (M2-1 mod m2) = 11*(11-1 mod 13) = 11 * 6 = 66
➢ Bước 5: A = (a1*c1 + a2*c2) mod 143 = (9*78+ 5*66) mod 143 = 31 (mod
143)
Vậy 60-1 mod (11*13) = 31
Bài 4: ((21100 + 33-1) * 4551) mod (7*9*11)
➢ Bước 1: A = ((21100 + 33-1) * 4551), M = (7*9*11), m1=7, m2=9, m3=11
➢ Bước 2:
o M1 = M/m1 = (7*9*11)/7 = 99
o M2 = M/m2 = (7*9*11)/9 = 77
o M3 = M/m3 = (7*9*11)/11 = 63
➢ Bước 3:

o a1= A mod m1 = ((21100 + 33-1) * 4551) mod 7 = 6
o a2= A mod m2 = ((21100 + 33-1) * 4551) mod 9 = 0
o a2= A mod m2 = ((21100 + 33-1) * 4551) mod 11 = 8
➢ Bước 4:
o c1 = M1 * (M1-1 mod m1) = 99*(99-1 mod 7)
➢
Bài 5: ((19125 + 2551) * 4721/37) mod (9*11*13)
Tự làm

18


Bài kiểm tra thường xuyên số 1
Bài tập 1: Tính 173-1 mod 1024 trên nghịch đảo vành Zn.
Bài tập 2: Tính 71130 mod 23
Bài tập 3: Tính 60-1 mod (11*13) theo công thức phần dư Trung Hoa
Bài tập 4: Dùng định lý Ferma và định lý ơle tính: 9190 mod 100

19