Mathematics 243, section 1 – Algebraic Structures Solutions for Practice Exam 3 November 27, 2006

I. A) By the definition of RSA systems, we need to know the prime factorization of m, which is m = 11·13 here. Then d is the multiplicative inverse of e = 17 mod (11−1)(13−1) = 120. We have

120 = 7 × 17 + 1.

This equation says 7 × 17 ≡ −1 mod 120, so d = 113 ≡ −7 mod 120.

B) We have H = 7 and C = 2 (starting from A = 0). Hence by repeated squaring,

7^{2} ≡ 49 mod 143, 7^{4} ≡ 113 mod 143, 7^{8} ≡ 42 mod 143, 7^{16} ≡ 48 mod 143

and

2^{2} ≡ 4 mod 143, 2^{4} ≡ 16 mod 143, 2^{8} ≡ 113 mod 143, 2^{16} ≡ 42 mod 143.

Hence

\begin{aligned}f(7) & = 7^{17} ≡ 7 · 7^{16} ≡ 7 · 48 ≡ 50 mod 143 \\ f(2) & = 2^{17} ≡ 2 · 2^{16} ≡ 2 · 42 ≡ 84 mod 143 \end{aligned}

The encrypted form is 050, 084 (with three-digit blocks).

II. The answer is yes. The operation ∗ defined here on the set of rational numbers other than −1 does satisfy all the properties needed for a group operation:

i. Q is closed under ∗ since if x = m/n and y = p/q are any two rational numbers,

x ∗ y = m/n + p/q + m/n · p/q = (mq + np + mp)/(nq)

is a quotient of integers – an element of Q. ii. The operation ∗ is associative: We have

(x ∗ y) ∗ z = (x + y + xy) ∗ z = x + y + xy + z + xz + yz + xyz

and

x ∗ (y ∗ z) = x ∗ (y + z + yz) = x + y + z + yz + xy + xz + xyz

are equal for all x, y, z ∈ Q (by commutativity of addition). iii. The element 0 ∈ Q is an identity element for ∗:

x ∗ 0 = x + 0 + x · 0 = x = 0 + x + 0 · x = 0 ∗ x

for all x. iv. If we try to find an inverse element for x ∈ Q, that is, a y such that

0 = x ∗ y = x + y + xy

we see y = \frac{−x}{1+x}. This is only defined if x ≠ −1. Since we removed x = −1, then the remaining elements of Q do form a group under this operation(!)

III. A) We’ll use the result that if G = ⟨a⟩ is a cyclic group of order n, then a^{k} is a generator for G if and only if gcd(k, n) = 1. (This follows, for instance from IV B below!). The additive group Z_{21} is cyclic with generator [1] for instance. Hence

[1], [2], [4], [5], [8], [10], [11], [13], [16], [17], [19], [20]

are all generators (for instance [5] = k · [1] and gcd(21, 5) = 1).

B) The elements from part A all have order 21. The elements [3], [6], [9], [12], [15], [18] all generate ⟨[3]⟩ and have order 7. The elements [7], [14] generate ⟨[7]⟩ and have order 3. [0] has order 1.

IV. A) Let G = ⟨a⟩, so H consists of some set of powers a^{k}. If H = {a^{0} = e}, then H = ⟨e⟩ is cyclic. Hence from now on we can assume that H contains some a^{k} for k > 0. Let m be the smallest strictly positive integer such that a^{m} ∈ H. We will show that H = ⟨a^{m}⟩, which will show that H is cylic. First ⟨a^{m}⟩ ⊆ H since H is a subgroup of G, hence closed under products and inverses. Conversely, suppose a^{n} ∈ H. In the integers, divide m into n, yielding

n = qm + r

for some unique integers q, r with 0 ≤ r ≤ m−1. We have a^{n} = a^{qm+r} = (a^{m})^{q} ·a^{r}. Hence

(1)  a^{r} = ((a^{m})^{q})^{−1} · a^{n}.

We are assuming a^{m} ∈ H and a^{n} ∈ H. Since H is a subgroup, it is closed under products and inverses, hence the equation (1) above shows that a^{r} ∈ H too. But we assumed that m was the smallest strictly positive integer such that a^{m} ∈ H. Hence r = 0, so n = qm and a^{n} = a^{mq} = (a^{m})^{q} ∈ ⟨a^{m}⟩. It follows that H ⊆ ⟨a^{m}⟩. Since we have both inclusions now, H = ⟨a^{m}⟩.

B) Since G is finite cyclic of order n with generator a, we have a^{n} = e. Let d = gcd(k, n). Then we know d = pk + qn for some integers p, q. It follows that

a^{d} = a^{pk+qn} = (a^{k})^{p} · (a^{n})^{q} = (a^{k})^{p} · e^{q} = (a^{k})^{p}

This shows that a^{d} ⊆ ⟨a^{k}⟩. Since ⟨a^{k}⟩ is a subgroup of G, it follows that ⟨a^{d}⟩ ⊆ ⟨a^{k}⟩ because the other elements of ⟨a^{d}⟩ are the powers of a^{d}. To see the other inclusion, note that d | k. Hence k = dm for some integer ℓ. Hence a^{k} = a^{dℓ} = (a^{d})^{ℓ} ∈ ⟨a^{d}⟩. Since ⟨a^{d}⟩ is a subgroup of G, it follows that ⟨a^{k}⟩ ⊆ ⟨a^{d}⟩.

V. A)

[x]_{12} = [y]_{12} ⇔ 12 | (x − y)
⇒ 3 | (x − y)
⇒ 9 | 3(x − y)
⇒ 9 | (3x − 3y)
⇒ [3x]_{9} = [3y]_{9}

B) We have by the definition of addition in Z_{12} and Z_{9}:

ϕ([x]_{12} + [y]_{12}) = ϕ([x + y]_{12})
= [3(x + y)]_{9}
= [3x + 3y]_{9}
= [3x]_{9} + [3y]_{9}
= ϕ([x]_{12}) + ϕ([y]_{12})

Hence ϕ is a group homomorphism.

C) The kernel of ϕ is the set of all elements of the domain mapping to the identity in the codomain:

ker(ϕ) = {[x]_{12} | ϕ([x]_{12}) = [0]_{9}} = {[0]_{12}, [3]_{12}, [6]_{12}, [9]_{12}}

VI. A) GL_{2}(R) is the group of invertible 2 × 2 matrices under matrix multiplication. We have

ab = ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ) ( \begin{matrix}1 & 2 \\ 3 & 4 \end{matrix} ) = ( \begin{matrix}4 & 6 \\ 3 & 4 \end{matrix} )

but

ba = ( \begin{matrix}1 & 2 \\ 3 & 4 \end{matrix} ) ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ) = ( \begin{matrix}1 & 3 \\ 3 & 7 \end{matrix} )

So ab ≠ ba and b ∉ C(a).

B) To show C(a) is a subgroup of G, we must show that C(a) is nonempty, and closed under products and inverses. First, ae = ea = a, so e ∈ C(a) no matter what a is. Hence C(a) ≠ ∅. If x, y ∈ C(a), then by associativity of the operation in G, the product xy satisfies:

a(xy) = (ax)y = (xa)y = x(ay) = x(ya) = (xy)a

Hence xy ∈ C(a). Finally, let x ∈ C(a). The equation ax = xa implies that x^{−1}(ax)x^{−1} = x^{−1}(xa)x^{−1}. But cancelling, this shows x^{−1}a = ax^{−1}. Hence x^{−1} ∈ C(a) too.