1. Limited time only! Sign up for a free 30min personal 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!

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