MAT1830 - Discrete Mathematics for Computer Science
Assignment #1
To be handed in at the beginning of your applied class in week 3 (23–27 March)
Show your working and give full explanations for all questions.
1. Are the following statements true or false? For each, explain why.
(a) 15 divides 5 [1]
(b) gcd(4, 16) = 2 [1]
(c) 46 ≡ 2 (mod 4) [1]
(d) For any positive even integer n, gcd(12, n) = 2. [2]
(e) For all integers x, if 10 does not divide x, then 10 does not divide 22x. [2]
(f) For all integers y, if gcd(9, y) = 3, then gcd(9, y2) = 9. [2]
[No marks without explanations]
2. Use the extended Euclidean algorithm to find integers x and y such that 1312x+ 400y = 32.
[6]
3. Let x and y be integers such that x ≡ 3 (mod 9) and y ≡ 4 (mod 9). Is it possible that
20x + 3y3 ≡ 6 (mod 9)? [5]