Vì p là số nguyên tố, p>3 nên p không chia hết cho 3
Vì p không chia hết cho 3 nên p có 1 trong 2 dạng: 3k+1, 3k+2(k thuộc N*)
Xét hai trường hợp:
+)p=3k+1(k thuộc N*)
Khi đó p2-1=(3k+1)2-1=9k2+6k+1-1=9k2+6k=3(3k2+2k)
Vì k thuộc N* nên 3k2+2k thuộc N*
Vì thế 3(3k2+2k) chia hết cho 3 nên p2-1 chi hết cho 3
+)p=3k+2(k thuộc N*)
Khi đó p2-1=(3k+2)2-1=9k2+12k+4-1=9k2+12k+3=3(3k2+4k+1)
vì k thuộc N* nên 3k2+4k+1 thuộc N*
Vì thế 3(3k2+4k+1) chia hết cho 3 nên p2-1 chia hết cho 3
Vậy nếu p là số nguyên tố lớn hơn 3 thì p2-1 chia hết cho 3
Giả sử là số nguyên tố lớn hơn , vì vậy p là số lẻ. Do đó, ta có thể biểu diễn p dưới dạng với là một số nguyên không âm.
Thay vào , ta có:
Ta nhận thấy rằng một trong hai số hoặc phải là số chẵn. Vì vậy, một trong hai số hoặc chia hết cho . Vì vậy, chia hết cho
Ngoài ra, vì p là số nguyên tố lớn hơn , nên p không chia hết cho . Vì vậy, và không thể đều chia hết cho . Do đó, hoặc phải chia hết cho . Vì vậy, chia hết cho .
Tổng hợp lại, chia hết cho và . Vì và nguyên tố cùng nhau, nên chia hết cho