Nghịch đảo modulo 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 thỏa mãn \((a \cdot x) \bmod m = 1\). Đây chính là phép "chia" trong số học modulo và giữ vai trò cốt lõi trong lý thuyết số, hệ mật mã RSA cùng nhiều thuật toán của lý thuyết mã hóa. Công cụ này tìm ra x bằng thuật toán Euclid mở rộng.
Cách sử dụng công cụ
Nhập số a và modulo m (với m ≥ 2). Công cụ sẽ trả về nghịch đảo x không âm nhỏ nhất trong khoảng 0 ≤ x < m, xác nhận nghịch đảo có tồn tại hay không và hiển thị gcd(a, m). Nếu gcd(a, m) ≠ 1 thì không có nghịch đảo và kết quả được báo là "Không có".
Giải thích công thức
Nghịch đảo chỉ tồn tại khi \(\gcd(a, m) = 1\), tức là a và m nguyên tố cùng nhau. Thuật toán Euclid mở rộng tìm các số nguyên x và y thỏa mãn \(a \cdot x + m \cdot y = \gcd(a, m)\). Khi gcd bằng 1, việc lấy x theo modulo m sẽ cho ra nghịch đảo:
$$\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}$$
Kết quả được chuẩn hóa thành giá trị dương bằng cách cộng thêm m nếu nó âm.
Ví dụ minh họa
Tìm nghịch đảo của 3 theo modulo 11. Ta cần x sao cho \(3x \equiv 1 \pmod{11}\). Thử nghiệm thấy:
$$3 \times 4 = 12 = 11 + 1 \quad\Longrightarrow\quad 12 \bmod 11 = 1$$
Vậy x = 4. Thuật toán Euclid mở rộng cũng cho cùng kết quả, và \(\gcd(3, 11) = 1\) khẳng định nghịch đảo có tồn tại.
Câu hỏi thường gặp
Khi nào không tồn tại nghịch đảo? Khi a và m có ước chung lớn hơn 1 — ví dụ 4 theo modulo 6 (\(\gcd = 2\)) không có nghịch đảo.
m có bắt buộc phải là số nguyên tố không? Không. m có thể là bất kỳ số nguyên nào ≥ 2; điều quan trọng duy nhất là a và m nguyên tố cùng nhau.
Kết quả nằm trong khoảng nào? Nghịch đảo được cho dưới dạng số dư không âm nhỏ nhất, nằm trong khoảng từ 0 đến m − 1.
