Explore BrainMass
Share

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
and
gcd(p,q) = 1
and
let a and b be integers with
0<=a <=p-1
and
0<=b<=p-1

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

© BrainMass Inc. brainmass.com October 24, 2018, 7:22 pm ad1c9bdddf
https://brainmass.com/math/discrete-math/solving-discrete-math-proofs-65118

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.

$2.19
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