Mục lục
1
1 Phần tử nghịch đảo
1.1 Vành
Trong lý thuyết số, vành được định nghĩa là vành thương của với quan hệ
đồng dư theo modulo m (là quan hệ tương đương) mà các phần tử của nó là các
lớp đồng dư theo modulo m (m là số nguyên dương lớn hơn 1). Ta cũng có thể
xét chỉ với các đại diện của nó. Khi đó
Phép cộng và nhân trong là phép toán thông thường được rút gọn theo
modulo m:
Trong lý thuyết số đã chứng minh rằng, số a là khả nghịch theo modulo m khi
và chỉ khi ƯCLN của a và m bằng 1.
Đẳng thức này lại chỉ ra y là nghịch đảo của a theo modulo m. Do đó có thể tìm
được phần tử nghịch đảo của a theo modulo m nhờ thuật toán Euclid mở rộng
khi chia m cho a.
1.2 Định nghĩa Phần tử nghịch đảo
Định nghĩa: Phần tử a của được gọi là khả nghịch trong hay khả
nghịch theo modulo m nếu tồn tại phần tử a' trong sao cho a*a'=1 trong
hay . Khi đó a' được gọi là nghịch đảo modulo m của a.
Tính chất:
• Cho a, b
∈
Z
n
. Phép chia a cho b theo modulo n là tích của a và b theo
modulo n, và chỉ được xác định khi b có nghịch đảo theo modulo n.
• Cho a
∈
Z
n
, a là khả nghịch khi và chỉ khi gcd (a, n) = 1.

Hệ quả: Nếu như p là số nguyên tố, thì bất kỳ số a, sao cho 0 < a < p, luôn
tồn tại phần tử nghịch đảo theo modulo p.
2 Thuật toán Euclide mở rộng
Giải thuật Euclid mở rộng sử dụng để giải phương trình vô định nguyên (còn
được gọi là phương trình Đi-ô-phăng)
a*x+b*y=c,
trong đó a, b, c là các hệ số nguyên, x, y là các ẩn nhận giá trị nguyên. Điều kiện
cần và đủ để phương trình này có nghiệm (nguyên) là UCLN(a, b) là ước của c.
Khẳng định này dựa trên một mệnh đề sau:
Trong số học đã biết rằng nếu d=UCLN(a, b) thì tồn tại các số nguyên x, y sao
cho
3
a'*x+b*y = d
2.1 Cơ sở lý thuyết của giải thuật
Giải thuật Euclide mở rộng kết hợp quá trình tìm ƯCLN(a, b) trong thuật toán
Eclid với việc tìm một cặp số x, y thoả mãn phương trình Đi-ô-phăng. Giả sử
cho hai số tự nhiên a, b, ngoài ra a>b>0. Đặt , chia cho
được số dư và thương số nguyên . Nếu thì dừng, nếu khác không,
chia cho được số dư , Vì dãy các là giảm thực sự nên sau hữu hạn
bước ta được số dư .
;
;
;
trong đó số dư cuối cùng khác 0 là . Bài toán đặt ra là tìm x, y sao
cho
Để làm điều này, ta tìm x, y theo công thức truy hồi, nghĩa là sẽ tìm
và sao cho:
với .
Ta có
và , nghĩa là

Me.Print d:=b, y
code
End Sub
Ví dụ 2.18 (Thuật toán Euclide mở rộng):
Tìm số nghịch đảo (nếu có) của 30 theo môđun 101
5
Bư
ớc
i
a b r q y0 y1 y
0
10
1
30 11 3 0 1 -3
1 30 11 8 2 1 -3 7
2 11 8 3 1 -3 7 -10
3 8 3 2 2 7 -10 27
4 3 2 1 1 -10 27 -37
5 2 1 0 . . . .
Kết quả tính toán trong bảng cho ta . Lấy số đối của theo mođun
được . Vậy .
2.3 Kết quả chương trình
Chương trình được viết bằng ngôn ngữ C++.
Dưới đây là kết quả đầu ra khi chạy chương trình.
Hình 1 : b không khả nghịch theo modulo a
6
Hình 2: b khả nghịch theo modulo a
7
Tài liệu tham khảo
1. Wikipedia />%ADt_Euclid_m%E1%BB%9F_r%E1%BB%99ng