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

    CompuChip

    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
    thx,guys
     
  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

    crd

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook