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

Intro to Abstract Math Question about divison of integers.

  1. Feb 13, 2012 #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 )

  2. jcsd
  3. Feb 13, 2012 #2
    Statement (1) is false. It becomes true if you add the assumption that gcd(a,b)=1.
  4. Feb 13, 2012 #3
    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. Feb 15, 2012 #4


    User Avatar
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook