a, b in Z, and p is prime

if p | ab

=> p | a or p | b

proof by contradiction:

assume p is not divided by a and p is not divided by b

p | ab =>  gcd(p, a) = 1  =>  xp + ya = 1  such that there exists x, y in Z(Eculidan algorithm)

since xp + ya = 1 => b(xp + ya) = b  =>  bxp + bya = b

since a | ab = > p | bya  and p | bxp

=> p | (bxp + bya)   => p | b

that contradict to our assumption