Định lý nhỏ Fermat là một định lý cơ bản trong lý thuyết số cơ bản, nó cung cấp các lũy thừa tính toán của các số nguyên modulo các số nguyên tố. Đây là một trường hợp cụ thể của định lý Euler, và rất cần thiết trong các ứng dụng của lý thuyết số cơ bản, chẳng hạn như kiểm tra tính cơ bản và mật mã khóa công khai. Đây được gọi là định lý nhỏ của Fermat.
Định lý Fermat còn được gọi là định lý nhỏ Fermat định nghĩa rằng P là số nguyên tố và ‘a’ là một số nguyên dương không chia hết cho P thì -
a P − 1 ≡ 1 bản mod P
Điều kiện thứ hai nói rằng nếu P là số nguyên tố và a là số nguyên thì P ≡ 1 bản mod P.
Bằng chứng - Z p là tập hợp các số nguyên {0, 1… P-1} khi nhân với modulo P, kết quả bao gồm tất cả các phần tử của Z p trong một dãy số nào đó, hơn nữa ax 0 ≡ 0 mod P. Do đó, các số (P-1) {a mod P, 2a mod P,… ((P-1) a mod P)} chỉ là số {1, 2 ,… (P-1)} theo một số thứ tự.
Nhân các số trong cả hai bước và lấy kết quả mà 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)! a P − 1
(P-1)! a P − 1 ≡ (𝑃 - 1)! mod P
a P − 1 ≡ 1 bản mod P
Xét tập hợp các số nguyên dương nhỏ hơn p:{1, 2 ... p1} và nhân từng phần tử với a, modulo p, nhận được tập X ={a mod p, 2a mod p. . . (p1) a mod p}. Không phần tử nào của X tương tự với 0 vì p không chia a.
Hơn nữa, không có hai số nguyên nào trong X giống nhau. Để thấy điều này, hãy xem xét rằng (ja ≡ p) trong đó 1 ≤ p1. Vì p, nó có thể xóa a khỏi cả hai vế của phương trình dẫn đến - j≡ p).
Sự tương tự cuối cùng này là không thể truy cập được do j và k đều là các số nguyên dương nhỏ hơn p. Do đó, cần hiểu rằng các phần tử (p1) của X đều là số nguyên dương, không có hai phần tử nào giống nhau.
Số - Định lý Fermat nói rằng nếu p là số nguyên tố và a là số nguyên dương không chia hết cho P thì a P − 1 ≡ 1 (mod p).
Do đó, 3 10 ≡ 1 (mod 11).
Do đó, 3 201 =(3 10 ) 20 x 3 ≡ 3 (mod 11).
Định lý nhỏ Fermats đôi khi có lợi cho việc nhanh chóng tìm ra lời giải cho một số lũy thừa. Các ví dụ sau đây cho thấy khái niệm.
Ví dụ1 - Tìm kết quả của 6 10 mod 11.
Giải pháp
Ở đây, chúng ta có 6 10 mod 11 =1. Đây là phiên bản đầu tiên của định lý nhỏ Fermat trong đó p =11.
Ví dụ2 - Tìm kết quả của 3 12 mod 11.
Giải pháp
Do đó số mũ (12) và môđun (11) không bằng nhau. Với phép thay thế, điều này có thể được xác định bằng cách sử dụng định lý nhỏ của Fermat.
3 12 mod11 =(3 11 x3) mod11 =(3 11 mod11) (3 mod 11) =(3x3) mod11 =9