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

Homework Help: Prime Number Proof

  1. Feb 6, 2007 #1
    1. Here is the problem I'm stuck on:

    Let q be a positive integer, q is greater than or equal to 2, let a and b be integers such that if q divides ab, then q divides a or q divides b. Show that q is a prime number.




    2. I know that q is prime if and only if 1 divides q and q divides q.



    3. I don't really know where to begin. Where might I go from here?
     
  2. jcsd
  3. Feb 6, 2007 #2

    StatusX

    User Avatar
    Homework Helper

    You want to show that if q is such that whenever q divides ab, q divides a or q divides b, then q must be prime. One way to do this is to show that if q is not prime, then it is not true that whenever q divides ab, q divides a or q divides b. Do you see why this is the same thing? This is called the contrapositive of the original statement.
     
  4. Feb 7, 2007 #3

    HallsofIvy

    User Avatar
    Science Advisor

    Notice that "if q divides ab then q divides a or q divides b" must be true for all numbers a, b. Suppose q was not prime. Can you use that to construct numbers a, b such that "q divides ab but q does not divide a or b separately". The easiest case to try is q= 6.
     
    Last edited by a moderator: Feb 8, 2007
  5. Feb 7, 2007 #4
    If I assume that q is prime, then that implies that there exist two integers ab such that q divides ab. It also must mean that a and b are both greater than 1 and less than q. If this is the case, then q does not divide a and q does not divide b (contrapositive: if q is not prime, then q divides ab implies q does not divide a and q does not divide b). Therefore p is prime?
     
  6. Feb 7, 2007 #5
    Just to nitpick a little bit (maybe a lot..) that definition can't be exactly right since it is trivially true for all integers.

    In other words it is true for all integers n that 1|n and n|n. You need to modify the definition to say something along the lines of that 1 and n are the only divisors or n, and n is not equal to 1.
     
  7. Feb 9, 2007 #6

    HallsofIvy

    User Avatar
    Science Advisor

    ??Given any integer q, there certainly exist many integers a, b such that q divides ab. That's not the point!

    No, there is nothing said here requiring that a and b be less than q. Indeed, if q divides either a or b, then one of them must be at least as large as q.

    ?? Where did p come from?? Did you mean "q". If so, you started by saying "If I assume q is prime". What you have proved is "If q is prime, then q is prime"! No, what you give is not the contrapositive of the statement you want to prove- because the statement you give is NOT true.

    One more time- you have misstated the problem itself:
    is not true.
    For example q= 6 is NOT a prime number but a= 5, b= 12 are numbers such that "if q (6) divides ab (60) then q divides a or q divides b (6 divides 12)".

    What you want to prove is
    As you have been told, it is sufficient to prove the "contrapositive": "if there exist integers a,b such that q divides ab but q does not divide either a or b." Suppose q= 6. Can you find a, b such that 6 divides ab but does not divide either a or b?
     
    Last edited by a moderator: Feb 9, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook