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
