Máy Tính Định Lý Nhỏ Fermat

Nhập phép tính

Cơ số (a)

Số nguyên tố (p)

Kết quả

a^(p-1) mod p

1

Equals 1 — Fermat's Little Theorem holds

a^p mod p	2
a mod p	2
p có phải số nguyên tố không?	Yes
gcd(a, p)	1

Định lý nhỏ Fermat là gì?

Định lý nhỏ Fermat (Fermat's Little Theorem) là một trong những nền tảng của lý thuyết số. Định lý phát biểu rằng nếu p là số nguyên tố và a là một số nguyên không chia hết cho p (tức là gcd(a, p) = 1), thì a lũy thừa (p − 1) sẽ chia cho p dư đúng bằng 1. Viết dưới dạng ký hiệu: \(a^{p-1} \equiv 1 \pmod{p}\). Một dạng tổng quát hơn đúng với mọi số nguyên a: \(a^{p} \equiv a \pmod{p}\).

$$a^{\,p-1} \equiv 1 \pmod{p} \qquad\Longrightarrow\qquad \text{Base }a^{\,\text{Prime }p-1} \bmod \text{Prime }p$$

Định lý nhỏ Fermat: nâng a lên lũy thừa p-1 quay về 1 theo modulo số nguyên tố p.

Cách sử dụng máy tính này

Bạn nhập giá trị cơ số a và giá trị p. Máy tính sẽ kiểm tra xem p có phải số nguyên tố hay không, tính gcd(a, p), đồng thời tính cả \(a^{p-1} \bmod p\) và \(a^{p} \bmod p\) bằng phương pháp lũy thừa modulo nhanh. Khi p là số nguyên tố và gcd(a, p) = 1, kết quả đầu tiên luôn bằng 1 — đúng như định lý khẳng định. Nếu các điều kiện này không thỏa, kết quả \(a^{p-1}\) sẽ hiển thị là n/a, bởi định lý không bảo đảm giá trị bằng 1 trong trường hợp đó.

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

Lũy thừa modulo hoạt động bằng cách bình phương cơ số liên tục rồi rút gọn theo modulo p, nhờ vậy ngay cả những số mũ rất lớn cũng được xử lý gọn gàng. Định lý này là cơ sở cho các phép kiểm tra tính nguyên tố (kiểm tra Fermat), phần toán học sinh khóa trong mã hóa RSA, và việc tính nghịch đảo modulo, vì \(a^{p-2} \bmod p\) chính là nghịch đảo của a theo modulo của một số nguyên tố p.

$$\begin{gathered} a^{\,p-1} \equiv 1 \pmod{p} \qquad\text{and}\qquad a^{\,p} \equiv a \pmod{p} \\[1.5em] \text{where}\quad \left\{ \begin{aligned} a &= \text{Base } a \\ p &= \text{Prime } p \quad (\text{prime},\ \gcd(a,p)=1) \end{aligned} \right. \end{gathered}$$

Quảng cáo

Ví dụ minh họa

Giả sử a = 2 và p = 7. Vì 7 là số nguyên tố và gcd(2, 7) = 1, ta kỳ vọng $$2^{6} \bmod 7 = 64 \bmod 7 = 1.$$ ✔ Dạng tổng quát cho $$2^{7} \bmod 7 = 128 \bmod 7 = 2,$$ đúng bằng \(a \bmod 7 = 2\). ✔

Ví dụ minh họa: bình phương liên tiếp và rút gọn mod p cho kết quả 1.

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

Nếu p không phải số nguyên tố thì sao? Định lý có thể không còn đúng. Máy tính sẽ đánh dấu p không phải số nguyên tố và chỉ có giá trị tổng quát \(a^{p} \bmod p\) là có ý nghĩa, nhưng không nhất thiết bằng a.

Nếu a là bội số của p thì sao? Khi đó gcd(a, p) ≠ 1, nên \(a^{p-1} \bmod p\) sẽ không bằng 1 (mà bằng 0). Dạng tổng quát \(a^{p} \equiv a\) vẫn đúng.

Có thể dùng để tìm nghịch đảo modulo không? Có — với số nguyên tố p, \(a^{p-2} \bmod p\) chính là nghịch đảo nhân của a theo modulo p.