Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to Proof?

  1. Mar 2, 2010 #1
    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.
  2. jcsd
  3. Mar 3, 2010 #2
    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: Mar 3, 2010
  4. Mar 3, 2010 #3


    User Avatar
    Science Advisor
    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.
  5. Mar 3, 2010 #4
  6. Mar 3, 2010 #5
    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...
  7. Mar 3, 2010 #6


    User Avatar

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook