Giả sử A là 1 số nguyên tố , A = 30 k + r với k,rεN và 0≤r<30.

Nếu r chia hết cho 2, 3 hoặc 5 thì A cũng chia hết cho 2, 3 (hoặc 5) nên A = 2, 3 hoặc 5 ( thỏa mãn)

Nếu r không chia hết cho 2, 3 và 5 : Giả sử r là hợp số thì r=r1.r2 với r1,r2 > 1.

Vì  r không chia hết cho 2, 3 và 5 nên r1,r2 cũng không chia hết cho 2, 3 và 5 ⇒r1,r2 ≥ 7

⇒r=r1.r2≥7.7=49 ( vô lý ).

Vậy r không phải là hợp số nên r = 1 hoặc r là số nguyên tố.