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: Disc. math/logic: division & modulus proofs

  1. Mar 18, 2010 #1
    1. The problem statement, all variables and given/known data
    Show that if a, b, c, and d are integers such that a | c and b | d, then ab | cd.

    Let m be a positive integer. Show that a mod m = b mod m if a ≡ b(mod m)

    2. Relevant equations
    | means "divides," so a | b means "a divides b" or "b can be divided by a"
    mod gets the remainder; a mod m means "the remainder after m is divided by a"
    ≡ means "is congruent to"

    3. The attempt at a solution
    For the proof of the first one, I can easily substitute real values:
    a = 4
    b = 3
    c = 16
    d = 9

    and from that I would get

    (4)(3) | (16)(9)
    12 | 144

    which is obviously 12, for which the statement holds true; however, since this is a universal proof and not an existential one, that statement is far from enough to prove it.

    For the proof of the second statement, I am unsure about how to treat a congruency in a proof like this.

    Proofs are probably my weakest point in this course, so thanks in advance for any help.
  2. jcsd
  3. Mar 18, 2010 #2


    User Avatar

    If a | c, then c = ma. In the same way, d = nb.
    The rest of the demonstration is up to you.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook