MAT 3343, APPLIED ALGEBRA, FALL 2002

Prof. P. Selinger

Problem 1 (10 points). For any integer a ∈ ℤ, define aℤ = {ax|x ∈ ℤ}. Prove: for all a, b ∈ ℤ, b|a if and only if aℤ ⊆ bℤ.

Problem 2. (a) (5 points) Find all solutions of 30x = 15 in ℤ_{55}. How many different solutions are there?

(b) (10 points) For given integers a, b, n ∈ ℤ, prove that the equation ax = b has a solution in ℤ_{n} if and only if gcd(a, n)|b.

Problem 3 (10 points). Find the general solution of the following system of equations in ℤ_{7}:

( \begin{matrix}2x + 3y + 4z = 5 \\ 3x + 4y + 6z = 0 \end{matrix} )

Problem 4 (10 points). Let R be a Euclidean ring. Suppose a, b, c ∈ R and gcd(a, b) = 1. Prove that a|bc implies a|c.

Problem 5 (10 points). Find the greatest common divisor of the following two polynomials in ℤ_{3}[x]:

\begin{aligned}p(x) & = & x^{5} + x^{4} + 2x^{3} + 2 \\ q(x) & = & x^{5} + x^{3} + x^{2} + x + 2 \end{aligned}

Problem 6 (10 points). Consider the (7, 4)-Hamming code with the following generator matrix G and parity check matrix H:

G = ( \begin{matrix}1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ) H = ( \begin{matrix}1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{matrix} )

(a) Encode the message 0011, 1101, 1111 using this code.

(b) Decode the message 1101010, 0110111, 0111101, correcting all single-bit errors.

Problem 7 (10 points). Recall that the factorial of n is defined as n! = 1 · 2 · 3 · . . . · (n − 1).

Show that if p is prime, then (p − 1)! ≡ −1(mod p). (Hint: (p − 1)! is the product of all the units in ℤ_{p}).

Problem 8. Let R be a Euclidean ring, and let a ∈ R be an element. On R, define a relation ∼ by x ∼ y ⟺ a|(x − y).

(a) (5 points) Prove that ∼ is an equivalence relation.

(b) (5 points) Prove that addition and multiplication are well-defined on R/∼ by [x]_{∼} + [y]_{∼} = [x + y]_{∼} and [x]_{∼}[y]_{∼} = [xy]_{∼}.

(c) (5 points) Prove that if a is irreducible, then R/∼ is a field.