Công Cụ Tính Nghịch Đảo Nhân Theo Modulo

Nhập phép tính

Số nguyên a

Modulo m

Kết quả

Nghịch đảo nhân

4

a^-1 mod m

gcd(a, m)	1
Nghịch đảo tồn tại	Có

Nghịch đảo nhân theo modulo m là gì?

Nghịch đảo nhân theo modulo của một số nguyên a theo modulo m là một số nguyên x nằm trong khoảng từ 1 đến m−1 thỏa mãn điều kiện \((a \cdot x) \bmod m = 1\). Nói cách khác, khi nhân a với x rồi chia cho m, ta thu được số dư đúng bằng 1. Đây chính là phép tương đương với việc "chia cho a" trong số học modulo, và nó đóng vai trò nền tảng trong lý thuyết số cũng như mật mã học (sinh khóa RSA, băm dữ liệu, Định lý số dư Trung Hoa và nhiều ứng dụng khác).

Modular arithmetic wraps the number line into a circle of m positions.

Cách sử dụng công cụ

Nhập số nguyên a và modulo m (m phải lớn hơn hoặc bằng 2). Công cụ sẽ rút gọn a theo modulo m, chạy thuật toán Euclid mở rộng và trả về nghịch đảo nếu nó tồn tại. Các giá trị âm của a được xử lý tự động bằng cách quy chúng về khoảng từ 0 đến m−1.

Giải thích công thức

Nghịch đảo chỉ tồn tại khi và chỉ khi \(\gcd(a, m) = 1\) — nghĩa là a và m không có ước chung nào khác ngoài 1 (chúng nguyên tố cùng nhau). Công thức tổng quát là:

$$\text{a} \cdot x \equiv 1 \pmod{\text{m}}, \quad x \text{ exists } \iff \gcd\!\left(\text{a},\, \text{m}\right) = 1$$

Thuật toán Euclid mở rộng tìm các số nguyên s và t thỏa mãn \(a \cdot s + m \cdot t = \gcd(a, m)\). Khi gcd bằng 1, hệ số s rút gọn theo modulo m chính là nghịch đảo cần tìm. Nếu \(\gcd(a, m) \neq 1\) thì không tồn tại nghịch đảo.

The extended Euclidean algorithm yields x satisfying a·x + m·y = 1.

Ví dụ minh họa

Hãy tìm nghịch đảo của 3 theo modulo 11. Ta cần tìm x sao cho \((3 \cdot x) \bmod 11 = 1\). Thử nghiệm cho thấy

$$3 \cdot 4 = 12, \quad 12 \bmod 11 = 1$$

Vậy nghịch đảo là 4. Thuật toán Euclid mở rộng cho ra kết quả tương tự ngay lập tức vì \(\gcd(3, 11) = 1\).

Multiplying a by its inverse x lands exactly on 1 after wrapping mod m.

Câu hỏi thường gặp

Khi nào không tồn tại nghịch đảo? Khi a và m không nguyên tố cùng nhau. Ví dụ, 4 không có nghịch đảo mod 8 vì \(\gcd(4, 8) = 4 \neq 1\).

Modulo có cần phải là số nguyên tố không? Không. Bất kỳ modulo nào cũng được, miễn là a nguyên tố cùng nhau với nó. Nếu m là số nguyên tố thì mọi số a khác 0 từ 1 đến m−1 đều có nghịch đảo.

Tại sao kết quả luôn nằm trong khoảng từ 1 đến m−1? Bởi vì ta rút gọn nghịch đảo theo modulo m để thu được biểu diễn dương nhỏ nhất chuẩn tắc.