Intro to Abstract Math Question about divison of integers.

  1. (1)Assume a, b and n are nonzero integers. Prove that n is divisible by ab if and
    only if n is divisible by a and n is divisible by b.


    I'm wrong and can't remember why. I spoke to the professor about it for ~ 1 minute so it seems to have slipped my mind, it was because in one case it's true and in the other it isn't here is my proof:

    (2)Let a,b and n be non zero integers and assume ab|n. Since ab|n and because a and b must be integers they must both be factors of n. Thus, if a|n or b|n is false then ab will not be a factor of n which means ab∤n.
    Thus, ab|n if and only a|n and b|n where a, b and n are non zero integers.


    But, then I pulled from a website "[if and only if ]means you must prove that A and B are true and false at the same time. In other words, you must prove "If A then B" and "If not A then not B". Equivalently, you must prove "If A then B" and "If B then A".

    I believe that (2) shows if Statement {A} then {B}.
    So how would you show if not Statement {a} then not {B}?

    I'm going to say
    Suppose ab ∤ n is true then a ∤ n and b∤n

    Let a = 10, b = 10, n = 10

    ab∤ n, but b|n and a|n

    The thing I don't understand is how does that disprove (1).

    So, the question I'm asking is: Is statement (1) considered true or considered false taken as is. Also, if you could rip my proof apart would be great help(don't hold back criticize away XD )


    Thanks
     
  2. jcsd
  3. Statement (1) is false. It becomes true if you add the assumption that gcd(a,b)=1.
     
  4. It's false, because you when you say if and only if it is the same things as

    If-And-Only-If Proofs
    Often, a statement we need to prove is of the form
    \X if and only if Y ." We are then required to do
    two things:
    1. Prove the if-part: Assume Y and prove X.
    2. Prove the only-if-part: Assume X, prove Y .

    taken from http://infolab.stanford.edu/~ullman/ialc/slides/slides1.pdf

    Did 1.

    But, number 2 is
    Assume n is divisible by b and n is divisible by a if n is divisible by ab


    Choose n = 8, b = 2 a = 3
    n is divisible by b and n is divisible by a but n is not divisible by ab

    so it's false
    thx norwegian i see what you mean
     
  5. Deveno

    Deveno 906
    Science Advisor

    8 is not divisible by 3.

    let's pick a better example, where a and b have "some factor in common".

    so suppose a = 6, and b = 15, and n = 30. then a|n (because 30 = 6*5), and b|n (because 30 = 15*2), but it's pretty obvious ab = 90 does NOT divide 30 (for one, it's bigger).

    in general, you only know that n is divisible by the least common multiple of a and b. in our example above, lcm(6,15) = 30, and indeed 30 divides 30.
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?