## Computer science assignment

### computer science

##### Description

CMPSC 360 - Assignment #7

due Tuesday, March 28, 2017, at the beginning of class

Complete a well-organized write-up with clear answers or proofs to the following. Demonstrate

appropriate work and justification of solutions. [Note: Your write-up will be evaluated on its math-

ematical correctness and completeness AND the quality and clarity of its presentation.]

Note: For assignment problems, collaboration with other people and use of online resources is

NOT permitted.

Questions for Assignment #7

1. Using prime factorizations, find the greatest common divisors and least common multiplies of

the following pairs

a) 1800 and 210

b) 22

· 3

4

· 5 · 11 and 24

· 3

2

· 5

2

· 7

3

. [You may express your answers in terms of their prime

factoizations.]

2. Using the Euclidean Algorithm, calculate gcd(1548, 480). Then express the greatest common

divisor as a linear combination of 1548 and 480.

3. Prove the following:

For relatively prime integers m and n greater than 1, there exists an integer t such that tn ≡

1 (mod m) .

4. Prove (using induction) that for every nonnegative integer n that

Xn

k=0

3(−5)k =

1

2

1 − (−5)n+1

5. Let n ≥ 2. Prove (using induction) that if A1, A2, . . . , An and B1, B2, . . . , Bn are sets such

that Ak ⊆ Bk for k = 1, 2, . . . , n, then

[n

k=1

Ak ⊆

[n

k=1

Bk