Nguồn: hackerearth
Số tự nhiên là số nguyên tố khi và chỉ khi .
Với :
Với :
, do là số nguyên tố.
Với :
Với :
, do là số nguyên tố.
Với :
Mệnh đề đúng với và . Ta giả sử .
Khi là số nguyên tố thì với mọi . Theo định lý Euler ta có:
Đặt . Với mỗi thì là duy nhất và để , mặt khác khi và chỉ khi hoặc nên ta có thể tạo ra cặp số phân biệt như vậy. Nhân tất cả các cặp với nhau ta được
Nếu là hợp số
tồn tại ước của trong khoảng
do
(vô lý).
Vậy phải là số nguyên tố.
Định lý Wilson cho ta cách tính nhanh khi là số nguyên tố.