Mathematics 243, section 3 – Algebraic Structures Exam 2 – November 2, 2012

I. Think of R^{2} (the set of ordered pairs of real numbers) as the ordinary Cartesian coordinate plane. Let R be the relation on R^{2} defined by

(x_{1}, y_{1})R(x_{2}, y_{2}) ⇔ x_{1}^{2} + y_{1}^{2} = x_{2}^{2} + y_{2}^{2}

A) (15) Show that R is an equivalence relation on R^{2}.

B) (5) Draw a picture of the equivalence class [(3, 4)] for this relation.

II. (20) Prove by mathematical induction: For all n ≥ 1,

\frac{1}{1 · 2 · 3} + \frac{1}{2 · 3 · 4} + ⋯ + \frac{1}{n(n + 1)(n + 2)} = \frac{n(n + 3)}{4(n + 1)(n + 2)}.

III. A) (15) Give the precise statement of the division algorithm in Z, and prove the existence

part.

B) (15) Use the Euclidean algorithm to find the integer d = gcd(456, 120) and express d in the form d = m · 456 + n · 120 for some integers m, n.

C) (15) Find all solutions x ∈ Z of the congruence 17x ≡ 5 mod 32.

IV. (15) Let a, b, c be integers. Show that if gcd(a, b) = 1 and a|(bc), then a|c.

Extra Credit (10) Give a proof that every positive integer n > 1 is a product of prime numbers using complete induction. (Note: a “product” here may consist of a single factor.)