MAT 3343, APPLIED ALGEBRA, FALL 2003

Answers to the Midterm

Problem 1. Let m, n ∈ ℤ and m ⩾ 0. Prove that m|n iff gcd(m, n) = m.

Answer: “⇒”: Suppose m|n. But also m|m, so m is a common divisor of m, n. To show that it is a greatest common divisor, assume k is another common divisor. But then k|m, hence m is a greatest common divisor. Thus m = ± gcd(m, n). Since m ⩾ 0, it follows that m = gcd(m, n).

“⇐”: Suppose gcd(m, n) = m. Then m is a common divisor of m, n, hence m|n.

Problem 2. How many solutions does the equation x^{2} = 9 have in ℤ_{77}? Find all solutions.

Answer: Since 77 = 7 · 11, and 7, 11 are relatively prime, we know by the Chinese Remainder Theorem that x^{2} ≡ 9(mod 77) if and only if

(1) x^{2} ≡ 9(mod 7) and
(2) x^{2} ≡ 9(mod 11).

Since 7 and 11 are prime, ℤ_{7} and ℤ_{11} are fields, and hence we know that (1) and (2) each have precisely two solutions modulo 7 and 11, respectively: x = ±3 in each case. Again by the Chinese Remainder Theorem, we get four solutions x_{1}, …, x_{4} of the original equation, satisfying

x_{1} ≡ +3(mod 7) x_{1} ≡ +3(mod 11)
x_{2} ≡ +3(mod 7) x_{2} ≡ −3(mod 11)
x_{3} ≡ −3(mod 7) x_{3} ≡ +3(mod 11)
x_{4} ≡ −3(mod 7) x_{4} ≡ −3(mod 11)

Thus, we clearly have x_{1} = 3 and x_{4} = −3. To determine x_{2}, we first use Euclid’s algorithm to find 1 = 2 · 11 − 3 · 7; thus, 22 ≡ 1(mod 7) and 22 ≡ 0(mod 11), and −21 ≡ 0(mod 7) and −21 ≡ 1(mod 11). It follows that x_{2} = 3 · 22 − 3 · (−21) = 129 ≡ 52 ∈ ℤ_{77}, and x_{3} = −52. Thus, the four solutions are:

{±3, ±52}.

Problem 3. My RSA public key is given by N = 35, e = 5.

(a) Encrypt the message [3, 31, 2].

Answer: For each M ∈ {3, 18, 2}, we have to calculate the element M^{e}(mod N). We have 3^{5} = 243 ≡ 33(mod 35), 31^{5} ≡ (−4)^{5} = −1024 ≡ 26(mod 35), and 2^{5} = 32. So the encrypted message is [33, 26, 32].

(b) What is my secret decryption key d?

Answer: e and d must satisfy ed ≡ 1(mod φ(N)). In this case, N = pq with p = 5 and q = 7, thus φ(N) = (p − 1)(q − 1) = 24. We use Euclid’s algorithm to find the inverse of 5 in ℤ_{24}, which happens to be d = 5.

Problem 4. Consider the following (n, k)-code over the alphabet A = ℤ_{2}:

C = {000000, 100011, 010101, 110110, 001110, 101101, 011011, 111000}.

(a) Is this a linear code? If yes, give a generator matrix for it.

Answer: Yes, because C is a subspace of ℤ_{2}^{6}. A possible generator matrix is

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

(b) What are n and k?

Answer: n = 6 and k = 3.

(c) What is the minimal Hamming distance of this code?

Answer: Since C is a linear code, its minimal Hamming distance is equal to its minimal Hamming weight, which is 3.

(d) How many single-bit errors does this code detect? How many can it correct?

Answer: Since the Hamming distance is 3, this code detects 2 single-bit errors, and it corrects 1

.

(e) Suppose that the following message is received on a noisy channel: 001000, 001100, 110110, 010011. What message was most likely sent?

Answer: We use the nearest neighbor method, looking in each case for a neighbor of Hamming distance 0 or 1. We find 000000, 001110, 110110, 011011.

Problem 5. Find the general solution of the following system of equations in ℤ_{2}:

( \begin{matrix}x & & & + & z & + & u & & & & & = & 0 \\ x & + & y & & & + & u & + & v & & & = & 0 \\ x & + & y & + & z & & & & & + & w & = & 0 \end{matrix} )

Answer: We use row operations to obtain a row-reduced form.

[ \begin{matrix}1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \end{matrix} ]

⟺ [ \begin{matrix}1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{matrix} ] (add r.1 to r.2 and r.3)

⟺ [ \begin{matrix}1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 \end{matrix} ] (add r.2 to r.3)

⟺ [ \begin{matrix}1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 \end{matrix} ] (add r.3 to r.1 and r.2)

We find that x, y, z are pivot variables and u, v, w are free variables. We let u = a, v = b, w = c, and we find x = b + c, y = a + c, and z = a + b + c. Thus, the most general solution is

(x, y, z, u, v, w) = (b + c, a + c, a + b + c, a, b, c),

or

(x, y, z, u, v, w) = a(0, 1, 1, 1, 0, 0)+b(1, 0, 1, 0, 1, 0)+c(1, 1, 1, 0, 0, 1).

Problem 6. In a commutative ring, assume that a ≠ b, a^{3} = b^{3}, and a^{2}b = ab^{2}. Prove that a^{2} + b^{2} is not invertible.

Answer: Note that (a − b)(a^{2} + b^{2}) = a^{3} − a^{2}b − b^{3} + ab^{2} = 0. Thus, if a^{2} + b^{2} were invertible, we would have a − b = (a − b)(a^{2} + b^{2})(a^{2} + b^{2})^{−1} = 0, contradicting a ≠ b.

Problem 7. Prove: every finite integral domain is a field.

Answer: Let R be a finite integral domain. This means R is a commutative ring with |R| > 1 and with no zero divisors. Let x ∈ R with x ≠ 0. We want to show that x is invertible. Consider the function f : R → R defined by f(y) = xy. It is one-to-one by the cancelation property, i.e., if f(y) = f(y′), then xy = xy′, thus x(y − y′) = 0, thus y − y′ = 0 (since x is not a zero divisor). Since f is a function between finite sets of equal cardinality, it follows that f is also onto. Therefore, there exists some y with f(y) = 1. But then xy = 1, so y is the desired inverse.