Máy tính nghịch đảo nhân theo modulo là gì?
Công cụ này tìm nghịch đảo nhân theo modulo của một số nguyên a theo modulo m — tức là số nguyên duy nhất x nằm trong khoảng \(0 \le x < m\) sao cho \(a \cdot x \equiv 1 \pmod{m}\). Máy tính sử dụng thuật toán Euclid mở rộng, đồng thời cũng trả về ước chung lớn nhất \(\gcd(a, m)\). Đây là kiến thức lý thuyết số thuần túy và cho kết quả như nhau ở mọi nơi; nó được dùng rộng rãi trong mật mã học (sinh khóa RSA), băm dữ liệu và giải các phương trình đồng dư tuyến tính.
Cách sử dụng
Nhập số nguyên a và một modulo dương m (nên dùng \(m \ge 2\) để có nghịch đảo duy nhất có ý nghĩa). Công cụ sẽ rút gọn a theo modulo m, chạy thuật toán Euclid mở rộng, rồi báo kết quả nghịch đảo cùng với \(\gcd(a, m)\). Nếu a và m không nguyên tố cùng nhau (\(\gcd \ne 1\)) thì không tồn tại nghịch đảo, và máy tính sẽ thông báo điều đó.
Giải thích công thức
Nghịch đảo tồn tại khi và chỉ khi \(\gcd(a, m) = 1\). Thuật toán Euclid mở rộng tìm các số nguyên s và t sao cho \(a \cdot s + m \cdot t = \gcd(a, m)\). Khi gcd bằng 1, ta có \(a \cdot s \equiv 1 \pmod{m}\), vì vậy nghịch đảo là
$$x = ((s \bmod m) + m) \bmod m$$được chuẩn hóa về số dư không âm nhỏ nhất.
Ví dụ minh họa
Với \(a = 7\), \(m = 4\): vì \(7 \equiv 3 \pmod{4}\), ta cần giải \(3x \equiv 1 \pmod{4}\). Áp dụng thuật toán Euclid mở rộng cho \((7, 4)\) ta được \(\gcd = 1\) và hệ số Bézout \(s = -1\), do đó
$$x = ((-1 \bmod 4) + 4) \bmod 4 = 3$$Kiểm tra lại:
$$7 \cdot 3 = 21 = 5 \cdot 4 + 1 \equiv 1 \pmod{4}$$Vậy đáp án là 3.
Câu hỏi thường gặp
Khi nào nghịch đảo không tồn tại? Chỉ khi \(\gcd(a, m) > 1\). Ví dụ \(a = 6\), \(m = 9\) có \(\gcd = 3\), nên không có nghịch đảo.
a có thể là số âm hoặc lớn hơn m không? Hoàn toàn được. Trước tiên ta rút gọn a theo modulo m; kết quả không đổi vì \(a \equiv a' \pmod{m}\).
Nếu m = 1 thì sao? Mọi số nguyên đều đồng dư với 0 theo modulo 1, nên nghịch đảo hiển nhiên bằng 0.
