Định lý Fermat nhỏ là định lý cơ bản trong lý thuyết số sơ cấp, cung cấp tính lũy thừa số nguyên modulo số nguyên tố. Là trường hợp đặc biệt của định lý Euler, và thiết yếu trong ứng dụng lý thuyết số sơ cấp, như kiểm tra số nguyên tố và mật mã khóa công khai. Điều này gọi là định lý Fermat nhỏ.
Định lý Fermat cũng gọi là định lý Fermat nhỏ định nghĩa: nếu P là số nguyên tố và 'a' là số nguyên dương không chia hết cho P thì:
aP-1 ≡ 1 (mod P)
Điều kiện thứ hai nói: nếu P là số nguyên tố và a là số nguyên thì aP ≡ 1 (mod P).
Chứng minh - Zp là tập số nguyên {0, 1...P-1} khi nhân với a modulo P, kết quả chứa tất cả phần tử Zp theo thứ tự nào đó, hơn nữa a x 0 ≡ 0 (mod P). Do đó, (P-1) số {a mod P, 2a mod P,...((P-1)a mod P)} chỉ là số {1, 2,...(P-1)} theo thứ tự nào đó.
Nhân các số trong cả hai bước và lấy kết quả mod P cho:
a x 2a x ... x ((P-1)a) = [(a mod P) x (2a mod P) x ... x ((P-1)a mod P)] mod P
= [1 x 2 x...x (P-1)] mod P
= (P-1)! mod P
Nhưng
a x 2a x...x ((P-1)a) = (P-1)! aP-1
(P-1)! aP-1 ≡ (P-1)! (mod P)
aP-1 ≡ 1 (mod P)
Xét tập số nguyên dương nhỏ hơn p: {1, 2... p-1} và nhân mỗi phần tử với a, modulo p, nhận tập X = {a mod p, 2a mod p ... (p-1)a mod p}. Không phần tử X nào bằng 0 vì p không chia a.
Hơn nữa không hai số nguyên trong X giống nhau. Để thấy, xét (ja ≡ p) với 1 ≤ p-1. Vì p, có thể xóa a cả hai vế phương trình cho - j≡ p).
Sự tương đồng cuối cùng này không thể vì j và k đều là số nguyên dương nhỏ hơn p. Do đó, hiểu (p-1) phần tử X đều là số nguyên dương, không hai phần tử giống nhau.
Số học - Định lý Fermat phát biểu: nếu p là số nguyên tố và a là số nguyên dương không chia hết cho P, thì aP-1 ≡ 1 (mod p).
Do đó, 310 ≡ 1 (mod 11).
Do đó, 3201 = (310)20 x 3 ≡ 3 (mod 11).
Định lý Fermat nhỏ đôi khi hữu ích tìm nhanh giải pháp cho một số lũy thừa. Ví dụ sau minh họa khái niệm.
Ví dụ 1 - Tìm kết quả 610 mod 11.
Giải pháp
Ở đây, 610 mod 11 = 1. Đây là phiên bản đầu tiên định lý Fermat nhỏ với p = 11.
Ví dụ 2 - Tìm kết quả 312 mod 11.
Giải pháp
Do lũy thừa (12) và modulus (11) không bằng nhau. Với thay thế này có thể định nghĩa dùng định lý Fermat nhỏ.
312 mod 11 = (311 x 3) mod 11 = (311 mod 11)(3 mod 11) = (3 x 3) mod 11 = 9