Is a Prime Number Always a Factor of a Product of Integers?

[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.

 

[CompuChip]

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.