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!

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
    Staff Emeritus
    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: 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
    Staff Emeritus
    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: Feb 9, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Prime Number Proof
  1. Prime number proof (Replies: 3)

Loading...