# How to Proof?

liangiecar
How to proof?
A prime number p is a factor of a non-zero product of integers a*b if and only if it is a facotr of a and/or b.

mrbohn1
The "if" direction is obvious. For the "only if", you need to use the fundamental theorem of arithmetic. Because a*b has a unique prime decomposition, if a prime p divides a*b then it must be one of the primes in the decomposition. The prime decomposition of a*b is just the product of the decompositions of a and b, so p must divide a and/or b.

This sounds like a homework question! In which case you will need to be a lot more rigorous when you write it out.

Last edited:
Homework Helper
One side is trivial: if p is a factor of a and/or b, then it is clearly a factor of a * b.

For the converse implication, the easiest way I can think of is using the unique decomposition of any integer into its prime factors.

liangiecar
thx,guys

g_edgar
Caution. Some proofs of unique factorization may use this property of primes. And then it would be illegitimate to use unique factorization in the proof of this...

crd
assume p is a factor of ab. then p|ab. since p is prime, euclid's lemma says p|a and/or p|b, thus p is a factor of a and/or b.