1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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 prove this?

  1. Feb 14, 2017 #1
    1. The problem statement, all variables and given/known data
    Prove or disprove: let a and b be integers and let p be a prime number. If p divides ab then p divides a or p divides b.

    2. Relevant equations
    pk=a
    a=pq+r

    3. The attempt at a solution
    Contrapositive: if p does not divide a and p does not divide b, then p does not divide ab.
    p divides a for some integer k; pk=a
    p does not divide a for some integer q and r; a=pq+r
    If p divides ab and p does not divide a, then p divides b.
    gcd(p,a)=1; there exists integers u and v such that pu+av=1.
     
  2. jcsd
  3. Feb 14, 2017 #2

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    To prove directly, rather than using contrapositive, apply the unique factorization theorem to factor ab and see where that gets you.
     
  4. Feb 14, 2017 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    What tools/results are you permitted to know/use?
     
  5. Feb 14, 2017 #4
    What do you mean?
     
  6. Feb 14, 2017 #5
    Hello.sorry if this is wrong....I thought it would only work if a and b are greater than zero and one of a and b is greater than P? I also don't understand the question, sure if a and b are both negative(as it says are in integers) p can divide the product, but not both individually using other factors which are only primes? right? so to use the factorisation of primes, I think a or b > 0, and a or b > P

    assuming just using two lists of primes for a and b.
     
    Last edited: Feb 14, 2017
  7. Feb 14, 2017 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I mean exactly what I say. Have you already seen some theorems about integers, primes, etc.? Do you know about prime factorization? So, what material do you have available to work with?
     
  8. Feb 14, 2017 #7

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Good point. To give a complete proof, the possibility of negative numbers needs to be considered. I think that can be taken care of by proving it for all positive numbers and handling negative numbers as corollaries.
     
  9. Feb 17, 2017 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    That is not a necessary additional condition.
     
  10. Feb 17, 2017 #9
    Yes, I think I understand. Is it because a= b =p is not ruled out??
     
  11. Feb 17, 2017 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, it's because you are given that p divides ab, so (if nonnegative) you can prove that at least one of them is greater than p.
     
  12. Feb 17, 2017 #11
    Oh, I think that is what I meant originally but now I am not sure as I said a or b > p and then one of a and b > p.,
    thank you, i must study the basics again.
     
    Last edited: Feb 17, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How to prove this?
  1. How to prove this. (Replies: 4)

  2. How to prove? (Replies: 1)

  3. How to prove? (Replies: 3)

Loading...