Explore BrainMass

Explore BrainMass

    Discrete math proofs

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Please help with the following proofs. Answer true or false for each along with step by step proofs.

    1) Prove that all integers a,b,p, with p>0 and q>0 that
    ((a+b) mod p)mod q = (a mod p) mod q + (b mod p) mod q
    Or give a counterexample

    2) prove for all integers a,b,p,q with p>0 and q>0 that
    ((a-b)mod p) mod q=0
    if and only if
    (a mod p) mod q = (b mod p) mod q
    Or give a counterexample.

    3) let p and q be positive integers with
    0 < p < q
    gcd(p,q) = 1
    let a and b be integers with
    0<=a <=p-1

    4) Prove that there exists an integer x such that
    (x mod p) mod q = a
    (x mod q) mod p = b

    © BrainMass Inc. brainmass.com March 4, 2021, 6:51 pm ad1c9bdddf

    Solution Preview

    1. False
    For example, a=3, b=5, p=7, q=17, then
    ((a+b) mod p) mod q=1
    (a mod p) mod q + (b mod p) mod q =3+5=8
    The equation does not hold.

    2. False.
    For example, a=3, b=-4, p=17, q=7, then
    ((a-b) mod p) mod q = ...

    Solution Summary

    There are several discrete math proofs in this solution. All of them involve integers and counter examples. The proofs are provided in step by step format.