Giả sử A là 1 số nguyên tố , A = 30 k + r với k,rεNk,rεN và 0≤r<300≤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.r2r=r1.r2 với r1,r2r1,r2 > 1.
Vì r không chia hết cho 2, 3 và 5 nên r1,r2r1,r2 cũng không chia hết cho 2, 3 và 5 ⇒r1,r2⇒r1,r2 ≥≥ 7
⇒r=r1.r2≥7.7=49⇒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ố.
giả sử số nguyên tố đó là A
ta có A = 30k + r (k,r ∈ N; 0 ≤ r ≤ 30)
với r ⋮ 2;3;5 thì A ⋮ 2;3;5 ⇒ A ∈ {2;3;5} (thỏa mãn)
với r không chia hết 2;3;5, giả sử r là hợp số
⇒ r = r1r2 (r1; r2 ∈ N*;r1; r2 >1)
⇒ r1; r2 không chia hết 2;3;5 ⇒ r1r2 ≥ 7.7 = 49 (vô lí)
ta có đpcm
