Introduction to Mathematical Reasoning (MATH 1800 A) – Fall 2020
Assignment 2
Due Wednesday, November 18, by 4 p.m.
Total: 30 marks.
1. [6 marks] Let a = 87 and b = 72. Find gcd(a, b), and write it in the form ax + by for some
x, y ∈ Z.
2. (a) [5 marks] Let a, b ∈ Z with gcd(a, b) = 1, and let c ∈ Z. Show the equivalence:
ab | c ⇔ a | c and b | c.
Hint: To prove the implication “⇐”, start from a | c and use the fact, due to gcd(a, b) = 1,
that for any k ∈ Z, if b | ka then b | k.
(b) [3 marks] Find integers a, b, c ∈ Z with gcd(a, b) 6= 1 where the equivalence in (a) does
not hold.
3. Let n ∈ Z.
(a) [4 marks] Let p be a prime number. Show the equivalence: p | n ⇔ p | n2.
(b) [4 marks] Show that if 4 | n, then 4 | n2. Show also that the converse is not true.
4. For each of the following relations on Z, check the properties of reflexivity, symmetry, and
transitivity, and deduce whether it is an equivalence relation (justify your answers by showing,
for each property, either that it holds, or that it does not hold):
(a) [4 marks] for all a, b ∈ Z, aRb if and only if a + b is even;
(b) [4 marks] for all a, b ∈ Z, aRb if and only if ab is even.

欢迎咨询51作业君