for p being natural prime number
for a being integer number holds
( a gcd p <> 1 iff p divides a )