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!

Prove Divisibility

  1. May 19, 2014 #1
    1. The problem statement, all variables and given/known data
    a.) Prove: If an integer ##a## does not divide ##bc##, then ##a## does not divide ##b## and ##a## does not divide ##c##.
    b.) State and either prove or disprove the converse of the above statement.

    3. The attempt at a solution
    a.) Proof by contrapositive
    ## a|c \vee a|b \implies a|bc \\ c=ak \vee b =ap ##


    Now, we multiply them by each other and
    ## bc = a(kap) , kap \in \mathbb{Z} ##

    So, it follows and the original statement in a is proved.

    b.) Now, the converse.
    ## a\not|c \wedge a\not |b \implies a \not | bc ##


    Can I say?
    ## a\not|c \wedge a\not |b ##
    ## c \not =ak \\ b \not = ap ##


    Multiply
    ##cb \not = a(kap) ## then
    ## a \not | cb, kap \in \mathbb{Z}##
     
  2. jcsd
  3. May 20, 2014 #2

    Curious3141

    User Avatar
    Homework Helper

    This is the correct contrapositive of the proposition you are asked to prove. But you shouldn't just state it like this (because it sounds like you're assuming it at the outset). You can preface the statement by: "We therefore need to show that the contrapositive holds, i.e....". Then the proof follows.

    This is wrong. Remember that you are using a logical disjunction (OR) denoted by ##\vee## in your contrapositive statement. That means that either the first condition OR the second (or both) are true. But it clearly may not be that BOTH are true simultaneously, which is what you're assuming by just multiplying out the expressions.

    Why not start with the first condition ##c=ak##, and just multiply that by ##b## to get ##bc = akb = (a).(kb)##? Then repeat the same with the other condition ##b=ap## and multiply by ##c##. Isn't that sufficient to prove the contrapositive, and therefore the original proposition?



    First of all, is the converse true or false? Hint: consider ##a, b## and ##c## to have just two prime factors each. Let's say ##a = pq, b = qr, c = pr##, where ##p,q,r## are all distinct primes. Now think about the implications to the converse proposition.
     
    Last edited: May 20, 2014
  4. May 20, 2014 #3
    You are right, it is sufficient.

    Given your conditions, the converse technically would be true, since ##(F \wedge F \implies F) \equiv T##
    Am I right?
     
  5. May 20, 2014 #4

    Curious3141

    User Avatar
    Homework Helper

    Check again. Are you sure that ##a \not | bc##?
     
  6. May 20, 2014 #5
    Sorry, I got confused.
    Let's see:

    ## a\not | c \wedge a\not | b \implies a \not |bc ##
    ## pr \not = pqx \wedge qr \not = pqy \implies pq(r^2) \not = pqz##
    ## T \wedge T \implies F \equiv F##
    So, the statement is false.
     
  7. May 20, 2014 #6

    Curious3141

    User Avatar
    Homework Helper

    Yes, the converse is false. I set those specific conditions so you would get a quick counter-example.

    One general suggestion: please tidy up (simplify) your notation. I find it very difficult to understand your mathematical statements.

    I would simply have written this as:

    ##a = pq, c = pr##

    Now, ##q \not | r \implies a \not | c##

    Also, ##a = pq, b = qr##

    So ##p \not | r \implies a \not | b##

    Hence the first two conditions are jointly satisfied.

    But ##bc = (pq).r^2 = a.r^2##. Hence ##a | bc##.

    Therefore, ##(a \not | b) \wedge (a \not | c) \not \Rightarrow (a \not | bc) ## and the converse is untrue.

    A little wordy, but I think it's much clearer. Just a suggestion.

    EDIT: I HATE LaTEX!
     
    Last edited: May 20, 2014
  8. May 20, 2014 #7
    I like LaTEX. Why do you hate it?
     
  9. May 20, 2014 #8

    Curious3141

    User Avatar
    Homework Helper

    Difficulty in usage, many quirks, and some unpredictability (e.g. some tags not accepted, some symbols not appearing as they should, etc.). This is a topic for another thread and off topic, let's end it here. :smile:
     
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: Prove Divisibility
Loading...