Question

Discrete Math

a) Find the quotient q and the remainder r as defined in the Division Algorithm so that a = qb + r where a = −65 and b = 11.

b) Find the gcd(1200, 560). Show some of your computations.

c) Prove that if b|a and b|c then b|(a + c).

Answer 1

Part c: Contained within the explanation

Part b: gcd(1200,560)=80

Part a: q=-6 r=1

Explanation:

I will start with c and work my way up:

Part c:

Proof:

We want to shoe that bL=a+c for some integer L given:

bM=a for some integer M and bK=c for some integer K.

If a=bM and c=bK,

then a+c=bM+bK.

a+c=bM+bK

a+c=b(M+K) by factoring using distributive property

Now we have what we wanted to prove since integers are closed under addition. M+K is an integer since M and K are integers.

So L=M+K in bL=a+c.

We have shown b|(a+c) given b|a and b|c.

//

Part b:

We are going to use Euclidean's Algorithm.

Start with bigger number and see how much smaller number goes into it:

1200=2(560)+80

560=80(7)

This implies the remainder before the remainder is 0 is the greatest common factor of 1200 and 560. So the greatest common factor of 1200 and 560 is 80.

Part a:

Find q and r such that:

-65=q(11)+r

We want to find q and r such that they satisfy the division algorithm.

r is suppose to be a positive integer less than 11.

So q=-6 gives:

-65=(-6)(11)+r

-65=-66+r

So r=1 since r=-65+66.

So q=-6 while r=1.