Nguồn: hackerearth
Số tự nhiên n>1 là số nguyên tố khi và chỉ khi (n−1)!≡n−1 (mod n).
-
Với n=4:
(n−1)! =6
(n−1)! mod n =2
-
Với n=5:
(n−1)! =24
(n−1)! mod n =4=n−1, do n là số nguyên tố.
-
Với n=6:
(n−1)! =120
(n−1)! mod n =0
-
Với n=11:
(n−1)! =3628800
(n−1)! mod n =10=n−1, do n là số nguyên tố.
-
Với n=12:
(n−1)! =39916800
(n−1)! mod 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 (mod n)
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 mod n
Đặt b=an−2modn. Với mỗi a thì b là duy nhất và b<n để a∗b (mod n) =1, 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 2(n−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) mod n=1
⇒ 1.2.3..(n−1) mod n=n−1
⇒(n−1)!≡n−1 (mod n)
- Chiều ngược: nếu (n−1)!≡n−1 (mod n) 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)! mod n khi n là số nguyên tố.