Nguồn: hackerearth
Số tự nhiên n>1 là số nguyên tố khi và chỉ khi (n−1)!≡n−1(modn).
-
Với n=4:
(n-1)! \bmod n = 2
-
Với n=6:
(n-1)! \bmod n = 0
-
Với n=12:
(n-1)! \bmod n = 0
Mệnh đề đúng với n=2 và n=3. Ta giả sử n>3.
- Chiều thuận: nếu n là số nguyên tố thì (n−1)!≡n−1(modn)
Khi n là số nguyên tố thì gcd(a,n)=1 với mọi a<n. Theo định lý Euler ta có:
a×an−2=an−1≡1(modn)
Đặt b=an−2modn. Với mỗi a thì b là duy nhất và b<n để a×b≡1(modn), mặt khác a=b khi và chỉ khi a=1 hoặc a=n−1 nên ta có thể tạo ra 2n−2 cặp số a,b phân biệt như vậy. Nhân tất cả các cặp với nhau ta được
2⋅3⋅4⋯(n−2)≡1(modn)
⇒1⋅2⋅3⋯(n−1)≡n−1(modn)
⇒(n−1)!≡n−1(modn)
- Chiều ngược: nếu (n−1)!≡n−1(modn) thì n là số nguyên tố
Nếu n là hợp số
⇒ tồn tại ước của n trong khoảng (2;n)
⇒gcd((n−1)!,n)>1 do (n−1)!=1⋅2⋅3⋯(n−1)
⇒gcd((n−1)!modn,n)>1
⇒gcd(n−1,n)>1 (vô lý).
Vậy n phải là số nguyên tố.
Định lý Wilson cho ta cách tính nhanh (n−1)!modn khi n là số nguyên tố.