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

Help with prime factorization proof

  1. Feb 29, 2004 #1
    I have to prove that if ab is divisible by the prime p, and a is not divisible by p, then b is divisible by p.

    In order to prove this, I have to show (a,p)=1. I am not sure what this statement means.

    Then I am supposed to use the fact that 1=sa + tp when s,t are elements of the set of integers. (This statement was already proved in class). Then I figured to multiply across by b so that we get

    b= sab + tpb. I am not sure where to from here. I have not seen to many proofs regarding prime factorization. Thanks

  2. jcsd
  3. Feb 29, 2004 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This means "The greatest common divisor of a and p is 1". You may have sometimes seen this written as gcd(a, p) = 1.

    Well, you want to know if p divides the LHS of this, and the LHS is equal to the RHS...
  4. Mar 1, 2004 #3
    If ab has a factor p and a don't, then b has the factor. That's logic.

    If a = c + id and b = e - id, it's a bit harder.
    Last edited: Mar 1, 2004
  5. Mar 1, 2004 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Every result in maths is 'just logic', surely.

    To show there is some content, consider Z{sqrt(5)]

    2 is prime

    2 divides 4=(sqrt5 - 1)(sqrt 5 +1)

    2 divides neither of the terms on the left as they are both prime too.

    so it important that the division algorithm works in Z. Or was that reference to x+iy some indiction of something in the ring Z?
    Last edited: Mar 1, 2004
  6. Jul 5, 2004 #5
    You are almost finished.

    Since you have already arrived at b=sab +tpb, we know that p divides tpb, and p divides sab so that p divides b.

    If there seems a need here for steps, we can look at p(sab/p +tb) =b. Since we know (sab/p +tb) is an integer, we see that b contains the factor p.
    Last edited: Jul 6, 2004
  7. Jul 6, 2004 #6
    Do you enjoy necromancing threads that are months old or something? :P
  8. Aug 4, 2004 #7
    Perhaps it's not true?
  9. Aug 5, 2004 #8
    I hoped I wasn't doing any harm. As for as good, well, I don't know. I thought it added for completeness.
  10. Aug 6, 2004 #9
    Oh no, I was just kidding around when I said that.
  11. Aug 6, 2004 #10


    User Avatar
    Staff Emeritus
    Science Advisor

    Perhaps WHAT'S not true?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Help with prime factorization proof
  1. Prime factorization (Replies: 2)

  2. Proof for primes help! (Replies: 5)