## Question

(a) a − b ≡ a' − b' (mod m), and

(b) ab ≡ a' b' (mod m).

2. Assume a, b, m, n are integers with m, n > 0 and n|m. Show if a ≡ b (mod m) then a ≡ b (mod n)

3. Show that if a, b, c are integers with c > 0 such that a ≡ b (mod c) then gcd(a, c) = gcd(b, c).

4. If p is prime, prove that x² ≡ y²(mod p) if and only if x ≡ y (mod p) or x ≡ −y (mod p). Is this true if p is not prime? Give a counter example.

5. What is the remainder if

(a) 7²¹³⁶ is divided by 8?

(b) 32¹⁴²³ is divided by 15?

6. Which of the following relations are equivalence relations?Either prove all three conditions hold or give a counter example for one of the conditions.

(a) Let S be the set of all sequences of 0s 1s and 2s of length 3. Define a relation R by xRy if and only if the sum of the entries in the sequences in x and y are equal. So (1, 2, 1) is related to (2, 2, 0) since the sum of the entries is 4.

(b) Let S = Z. Define a relation R by x Ry if and only if x − y is odd.

(c) Let S = Z and define aRb if and only if |a − b| ≤ 5.

(d) Let S = R² and define (x, y) R (a, b) if and only if x² + y² = a² + b².

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.