MAT 3343, APPLIED ALGEBRA, FALL 2003

Answers to the Final Exam

Problem 1. Suppose d and k are integers such that d > 0, d|(11k + 4), and d|(10k + 3). Show that d = 1 or d = 7.

Answer: Under the given hypotheses, we know that d|10(11k + 4) + (−11)(10k + 3).. Therefore d|110k + 40 − 110k − 33, hence d|7. Since 7 is prime, we have d = 1 or d = 7.

Problem 2. (a) Show that no integer of the form k^{2} + 1 is a multiple of 7.

Answer: The equation 7|(k^{2} + 1) is equivalent to k̄^{2} + 1 ≡ 0(mod 7), or k̄^{2} ≡ −1(mod 7). The squares in ℤ_{7} are 0^{2} = 0, 1^{2} = (−1)^{2} = 1, 2^{2} = (−2)^{2} = 4, 3^{2} = (−3)^{2} = 9 = 2. Hence no square in ℤ_{7} is equal to −1.

(b) Find all integers k such that k^{2} + 1 is a multiple of 13.

Answer: As in part (a), this is equivalent to finding all k such that k̄^{2} ≡ −1(mod 13). We examine all squares in ℤ_{13}: 0^{2} = 0, 1^{2} = (−1)^{2} = 1, 2^{2} = (−2)^{2} = 4, 3^{2} = (−3)^{2} = 9, 4^{2} = (−4)^{2} = 16 = 3, 5^{2} = (−5)^{2} = 25 = −1. We may stop here, as we have found two solutions k̄ = ±5, and ℤ_{13} is a field and therefore a quadratic equation has no more than 2 solutions. Thus, the general solution is k̄ ≡ ±5(mod 13). This means, the general integer solution is k ∈ {5 + 13a, −5 + 13a | a ∈ ℤ}, or k ∈ {…, −8, −5, 5, 8, 18, 21, …}.

Problem 3. Consider the following set of real 2 × 2-matrices:

R = \{( \begin{matrix}a & b \\ −b & a \end{matrix} ) | a, b ∈ ℝ\} .

(a) Show that R is a commutative ring, with the usual operations of addition and multiplication of matrices. (You may assume common properties of matrices without proof).

Answer: We already know that the set of all 2×2-matrices forms a (non-commutative) ring. Thus, it suffices to check that R is a subring, and that R is commutative. To check that it is a subring, we must check that it contains 0 and 1, and is closed under addition, multiplication, and negation. We

note that 0 ∈ R and 1 ∈ R. Further, if A = ( \begin{matrix}a & b \\ −b & a \end{matrix} ) and B = ( \begin{matrix}c & d \\ −d & c \end{matrix} ), then

A + B = ( \begin{matrix}a + c & b + d \\ −(b + d) & a + c \end{matrix} ) ∈ R

−A = ( \begin{matrix}−a & −b \\ b & −a \end{matrix} ) ∈ R

AB = ( \begin{matrix}ac − bd & ad + bc \\ −(ad + bc) & ac − bd \end{matrix} ) ∈ R

Finally we check commutativity:

BA = ( \begin{matrix}ac − bd & ad + bc \\ −(ad + bc) & ac − bd \end{matrix} ) = AB.

(b) Is R a field? Prove or give a counterexample.

Answer: Each matrix in R has determinant a^{2} + b^{2}, and thus it is invertible unless a = b = 0. It remains to check that the inverse is indeed in R. But we have

( \begin{matrix}a & b \\ −b & a \end{matrix} )^{−1} = \frac{1}{a^{2} + b^{2}} ( \begin{matrix}a & −b \\ b & a \end{matrix} ) ,

hence, the inverse is in R (if (a, b) ≠ (0, 0)). Thus, R is a field. (Note: R is indeed isomorphic to

the field of complex numbers ℂ, via the isomorphism a + bi ↦ ( \begin{matrix}a & b \\ −b & a \end{matrix} )).

Problem 4. Recall that the factorial of n is defined as n! = 1 · 2 · 3 · . . . · n.

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

Answer: Consider the units 1, 2, …, p − 1 in ℤ_{p}. Since the equation x^{2} = 1 has at most two roots, there are at most two elements which are their own inverse: these elements are 1 and −1. The set of remaining units can be divided into pairs of numbers that are mutually inverse. Now consider the product of all units. The mutually inverse pairs cancel out to 1, so the product of all units is equal to 1 · −1 = −1.

Problem 5. My RSA public key is given by (N, e) = (55, 27).

(a) What is my secret decryption key d?

Answer: We have N = pq = 5 · 11. The encryption and decryption keys satisfy the relation ed ≡ 1(mod φ(N)), where φ(N) = (p − 1)(q − 1) = 4 · 10 = 40. Thus 27d ≡ 1(mod 40). We use Euclid’s algorithm to solve this, and we find

\begin{aligned}40 & = & 1 · 27 & + & 13 \\ 27 & = & 2 · 13 & + & 1 \end{aligned}

Thus, 1 = 27 − 2 · 13 = 27 − 2 · (40 − 27) = 3 · 27 − 2 · 40. It follows that 27 · 3 ≡ 1(mod 40), thus d = 3.

(b) Decrypt the message [1; 4; 10].

Answer: We must compute 1^{3}, 4^{3}, and 11^{3} (mod 55). Clearly 1^{3} = 1, and 4^{3} = 64 ≡ 9(mod 55). Also, 10^{3} = 1000 ≡ 10(mod 55). So the decrypted message is [1; 9; 10].

Problem 6. Find all integers x which satisfy the following two equations simultaneously:

\begin{matrix}x^{2} ≡ 4(mod 7) \\ x^{3} ≡ x(mod 5) \end{matrix}

Justify your answer.

Answer: The first equation is equivalent to x^{2} − 4 ≡ 0(mod 7), or (x + 2)(x − 2) ≡ 0(mod 7), therefore x ≡ ±2(mod 7). The second equation is equivalent to x^{3} − x ≡ 0(mod 5), hence x(x^{2} − 1) ≡ 0(mod 5), hence x(x + 1)(x − 1) ≡ 0(mod 5), hence x ∈ {0, −1, 1}(mod 5). By the Chinese Remainder Theorem, each combination gives exactly one solution in ℤ_{35}, hence there is a total of 6 solutions:

x ≡ 2(mod 7), x ≡ 0(mod 5) ⟺ x ≡ −5(mod 35)
x ≡ 2(mod 7), x ≡ 1(mod 5) ⟺ x ≡ 16(mod 35)
x ≡ 2(mod 7), x ≡ −1(mod 5) ⟺ x ≡ 9(mod 35)
x ≡ −2(mod 7), x ≡ 0(mod 5) ⟺ x ≡ 5(mod 35)
x ≡ −2(mod 7), x ≡ −1(mod 5) ⟺ x ≡ −16(mod 35)
x ≡ −2(mod 7), x ≡ 1(mod 5) ⟺ x ≡ −9(mod 35)

Thus, the general solution set is {−16, −9, −5, 5, 9, 16} + 35ℤ.

Problem 7. Which of the following polynomials are irreducible in ℚ[x]? Give reasons.

(a) x^{5} + x^{3} + x^{2} + 1.

Answer: Not irreducible, because x^{5} + x^{3} + x^{2} + 1 = (x^{3} + 1)(x^{2} + 1). Also, because −1 is a root.

(b) x^{4} + 2x^{2} + 4x − 6.

Answer: Irreducible by Eisenstein’s criterion with p = 2. Note that p = 2 divides all coefficients but the highest one, and p^{2} = 4 does not divide the lowest coefficient (−6).

(c) x^{3} + x^{2} − 7.

Answer: Irreducible. By the rational root theorem, the only possible rational roots for this polynomial are ±1, ±7. It is quickly checked that these are not in fact roots. Hence, x^{3} + x^{2} − 7 has no linear factors in ℚ[x], and therefore it must be irreducible.

(d) x^{5} + 12x^{4} + 18x^{3} + 30x + 12.

Answer: Irreducible by Eisenstein’s criterion with p = 3. Note that Eisenstein’s criterion with p = 2 does not apply, because 2^{2} = 4 divides the lowest coefficient, a_{0} = 12.

Problem 8. Consider the polynomial (8, 4)-code with generating polynomial p(x) = x^{4} + x^{3} + x^{2} + 1.

(a) Find the generating matrix for this code (make sure that your generating matrix generates a systematic code).

Answer: We need to find the codewords corresponding to the four basis plaintext words (1, 0, 0, 0), (0, 1, 0, 0), and so forth. Thus, we need to represent each plaintext as a polynomial, multiply by x^{4}, and add the remainder of the division by p(x). We get:

\begin{aligned}(1000) → x^{3} → x^{7} = (x^{4} + x^{3} + x^{2} + 1)(x^{3} + x^{2} + 1) + 1 & → (10000001) \\ (0100) → x^{2} → x^{6} = (x^{4} + x^{3} + x^{2} + 1)(x^{2} + x) + x^{3} + x^{2} + x & → (01001110) \\ (0010) → x^{1} → x^{5} = (x^{4} + x^{3} + x^{2} + 1)(x + 1) + x^{2} + x + 1 & → (00100111) \\ (0001) → x^{0} → x^{4} = (x^{4} + x^{3} + x^{2} + 1)(1) + x^{3} + x^{2} + 1 & → (00011101) \end{aligned}

Thus, the generator matrix is

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

(b) For i = 1, …, 8, let r_{i}(x) be the remainder of the division of x^{8−i} by p(x). Let H be the matrix whose ith row is r_{i}(x), represented as a vector in ℤ_{2}^{4}. Find H, and prove that it is a parity check matrix for the code from (a).

Answer: The respective remainders are: r_{1}(x) = 1, r_{2}(x) = x^{3} + x^{2} + x, r_{3}(x) = x^{2} + x + 1, r_{4}(x) = x^{3} + x^{2} + 1 (these were calculated in part (a)), and r_{5}(x) = x^{3}, r_{6}(x) = x^{2}, r_{7}(x) = x, r_{8}(x) = 1. These remainders are simply the syndromes for each possible single-bit error, and thus they form the rows of a parity check matrix. We get

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

(c) What is the minimum Hamming weight of this code? Thus how many errors does it correct/detect?

Answer: It is easy to see that each codeword has even weight. Moreover, there is a codeword of weight 2, so the minimum Hamming weight is 2. The code detects 1 errors and corrects 0.

Problem 9. Consider the linear code with generator matrix

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

Find the coset of the received word (0, 0, 1, 0, 1). What is the coset leader? What is therefore the most likely corrected codeword?

Answer: Let w = (00101). The coset is

{vG + w|v ∈ ℝ^{3}} = {00101, 10110, 01100, 11110, 00011, 10000, 01010, 11000}.

The natural coset leader is (10000), since it has the smallest Hamming weight (and thus is the most likely error, assuming that errors occur independently in each bit). Therefore, the most likely corrected codeword is (00101) + (10000) = (10101) = (101)G.

Problem 10. Find the greatest common divisor of x^{4}+x^{3}+2x^{2}+x+1 and x^{4}+2x^{3}+3x^{2}+2x+2 in ℝ[x]. Answer: We use Euclid’s algorithm.

\begin{aligned}(x^{4} + 2x^{3} + 3x^{2} + 2x + 2) & = & (x^{4} + x^{3} + 2x^{2} + x + 1)(1) & + & (x^{3} + x^{2} + x + 1) \\ (x^{4} + x^{3} + 2x^{2} + x + 1) & = & (x^{3} + x^{2} + x + 1)(x) & + & (x^{2} + 1) \\ (x^{3} + x^{2} + x + 1) & = & (x^{2} + 1)(x + 1) & + & 0 \end{aligned}

Therefore, the greatest common divisor is x^{2} + 1. Problem 11. Consider the Galois Field GF(9), and let α be an element with α^{2} + 2α + 2 = 0.

(a) Is α a primitive element? Answer: We first make a representation of the Galois Field GF(9).

\begin{aligned}α^{0} & = & 1 & 01 \\ α^{1} & = & α & 10 \\ α^{2} & = & α + 1 & 11 \\ α^{3} & = & 2α + 1 & 21 \\ α^{4} & = & 2 & 02 \\ α^{5} & = & 2α & 20 \\ α^{6} & = & 2α + 2 & 22 \\ α^{7} & = & α + 2 & 12 \\ α^{8} & = & 1 & 01 \end{aligned}

We find that α is indeed a primitive element.

(b) Find all primitive elements in GF(9). Answer: Since α is primitive and of order 8, it follows that the primitive elements are of the form α^{i}, where gcd(i, 8) = 1, so α^{3}, α^{5}, and α^{7}.

(c) Find an irreducible polynomial which has α + 1 as a root. Answer: Let x = α + 1 = α^{2}. Then x^{0} = 1, x^{1} = α^{2} = α + 1, x^{2} = α^{4} = 2. We get a linear dependency, namely x^{2} + 1 = 0. So x^{2} + 1 has α + 1 as a root. Since it is the smallest degree polynomial with this property, it is irreducible. Problem 12. Find the generator polynomial of a 4-error correcting (31, k) BCH code. Note that a representation of GF(32) can be found on the attached sheet (page 6). What is the plaintext length k of this code? Answer: First, we find irreducible polynomials p_{i}(x) for p_{i}(α^{i}) = 0, for i = 1, 3, 5, 7. We have p_{1}(x) = x^{5} + x^{2} + 1. For p_{3}(x), let x = α^{3}, and calculate x^{n} for various n:

\begin{matrix}x^{0} = α^{0} = 1 & (00001) \\ x^{1} = α^{3} & (01000) \\ x^{2} = α^{6} = α^{3} + α & (01010) \\ x^{3} = α^{9} = α^{4} + α^{3} + α & (11010) \\ x^{4} = α^{12} = α^{3} + α^{2} + α & (01110) \\ x^{5} = α^{15} = α^{4} + α^{3} + α^{2} + α + 1 & (11111) \end{matrix}

We find a linear dependency between these 6 vectors: x^{5} + x^{4} + x^{3} + x^{2} + 1 = 0 has α^{3} as a root. Since x^{0}, …, x^{4} are linearly independent, no smaller-degree polynomial has α^{3} as a root, and thus p_{3}(x) = x^{5} + x^{4} + x^{3} + x^{2} + 1 is irreducible. For p_{5}(x), let x = α^{5}, and calculate:

\begin{matrix}x^{0} = α^{0} = 1 & (00001) \\ x^{1} = α^{5} & (00101) \\ x^{2} = α^{10} & (10001) \\ x^{3} = α^{15} & (11111) \\ x^{4} = α^{20} & (01100) \\ x^{5} = α^{25} & (11001) \end{matrix}

We find a linear dependency between these 6 vectors, which is p_{5}(x) = x^{5} + x^{4} + x^{2} + x + 1. For p_{7}(x), let x = α^{7}, and calculate:

\begin{matrix}x^{0} = α^{0} = 1 & (00001) \\ x^{1} = α^{7} & (10100) \\ x^{2} = α^{14} & (11101) \\ x^{3} = α^{21} & (11000) \\ x^{4} = α^{28} & (10110) \\ x^{5} = α^{35} & (10000) \end{matrix}

We find a linear dependency between these 6 vectors, which is p_{7}(x) = x^{5} + x^{3} + x^{2} + x + 1. Therefore, the generator polynomial is

\begin{aligned}p(x) & = & gcd(p_{1}(x), p_{3}(x), p_{5}(x), p_{7}(x)) \\ & = & (x^{5} + x^{2} + 1)(x^{5} + x^{4} + x^{3} + x^{2} + 1)(x^{5} + x^{4} + x^{2} + x + 1)(x^{5} + x^{3} + x^{2} + x + 1). \end{aligned}

which is of degree 20, thus the plaintext length is 11.

Attachment: Representation of GF (32) with α^{5} = α^{2} + 1

\begin{aligned}α^{0} & = & 1 & 00001 \\ α^{1} & = & α & 00010 \\ α^{2} & = & α^{2} & 00100 \\ α^{3} & = & α^{3} & 01000 \\ α^{4} & = & α^{4} & 10000 \\ α^{5} & = & α^{2} + 1 & 00101 \\ α^{6} & = & α^{3} + α & 01010 \\ α^{7} & = & α^{4} + α^{2} & 10100 \\ α^{8} & = & α^{3} + α^{2} + 1 & 01101 \\ α^{9} & = & α^{4} + α^{3} + α & 11010 \\ α^{10} & = & α^{4} + 1 & 10001 \\ α^{11} & = & α^{2} + α + 1 & 00111 \\ α^{12} & = & α^{3} + α^{2} + α & 01110 \\ α^{13} & = & α^{4} + α^{3} + α^{2} & 11100 \\ α^{14} & = & α^{4} + α^{3} + α^{2} + 1 & 11101 \\ α^{15} & = & α^{4} + α^{3} + α^{2} + α + 1 & 11111 \end{aligned} \begin{aligned}α^{16} & = & α^{4} + α^{3} + α + 1 & 11011 \\ α^{17} & = & α^{4} + α + 1 & 10011 \\ α^{18} & = & α + 1 & 00011 \\ α^{19} & = & α^{2} + α & 00110 \\ α^{20} & = & α^{3} + α^{2} & 01100 \\ α^{21} & = & α^{4} + α^{3} & 11000 \\ α^{22} & = & α^{4} + α^{2} + 1 & 10101 \\ α^{23} & = & α^{3} + α^{2} + α + 1 & 01111 \\ α^{24} & = & α^{4} + α^{3} + α^{2} + α & 11110 \\ α^{25} & = & α^{4} + α^{3} + 1 & 11001 \\ α^{26} & = & α^{4} + α^{2} + α + 1 & 10111 \\ α^{27} & = & α^{3} + α + 1 & 01011 \\ α^{28} & = & α^{4} + α^{2} + α & 10110 \\ α^{29} & = & α^{3} + 1 & 01001 \\ α^{30} & = & α^{4} + α & 10010 \\ α^{31} & = & 1 & 00001 \end{aligned}