Explore BrainMass

Discrete math proofs

This content was STOLEN 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 October 24, 2018, 7:22 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.

See Also This Related BrainMass Solution

Discrete Math: Proof using Mathematical Induction

1.Use mathematical induction to prove that 2-2*7+2*7^2-.....+2(-7)^n=(1-(-7)^n+1)/4 whenever n is a nonnegative integer.

2.Show that 1^3+2^2+....n^3=[n(n+1)/2]^2 whenever n is a positive integer.

3.Use mathematical induction to show that 3 divides n^3+2n whenever n is a nonnegative integer.

View Full Posting Details