714
Modeling Arithmetic, Computation, and Languages
“power” of 1, and 3Z, + 4 is cyclic with generator 1. Prove that the group 3Z 7 , + 7 4 is cyclic with
generator 2.
c. Prove that 5 is also a generator of the cyclic group 3Z 7 , + 7 4.
d. Prove that 3 is a generator of the cyclic group 3Z 4 , + 4 4.
42. Let 3G, # 4 be a cyclic group with generator a (see Exercise 41). Show that G is commutative.
43. a. Let 3S, # 4 be a semigroup. An isomorphism from S to S is called an automorphism on S. Let Aut(S) be
the set of all automorphisms on S, and prove that Aut(S) is a group under function composition.
b. For the group 3Z 4 , + 4 4, find the set of automorphisms and show its group table under + .
44. Let 3G, # 4 be a commutative group with identity i. Prove that the function f: G S G given by f (x) = x
−1
is an isomorphism.
45. Let f be a homomorphism from a group G onto a group H. Show that f is an isomorphism if and only if
the only element of G that is mapped to the identity of H is the identity of G.
46. Let 3G, # 4 be a group and g a fixed element of G. Define f: G S G by f(x) = g # x # g
−1
for any x [ G.
Prove that f is an isomorphism from G to G.
47. a. Consider the equivalence relation on the integers of congruence modulo n defined in Section 5.1. If
n = 5, there are 5 equivalence classes:
304 = 5… , −10, −5, 0, 5, 10, …6
314 = 5… , −9, −4, 1, 6, 11, …6
324 = 5… , −8, −3, 2, 7, 12, …6
334 = 5… , −7, −2, 3, 8, 13, …6
344 = 5… , −6, −1 ,4, 9, 14, …6
Let E 5 = 5 30 4, 314, 324, 33 4, 34 4 6. An operation + is defined on E 5 by
3x 4 + 3y 4 = 3x + y 4
For example, 324 + 344 = 32 + 4 4 = 36 4 = 31 4 (recall that an equivalence class can be named by any
of its elements). Prove that 3E 5 , + 4 is a commutative group.
b. 3Z 5 , + 5 4 is a commutative group with elements 50, 1, 2, 3, 46 (see Example 7). Prove that 3Z 5 , + 5 4 is
isomorphic to the group 3E 5 , + 4.
c. Results a and b hold for any value of n. In the group E 14 , what is the inverse of [10]? What is the preimage of [21] under the isomorphism from Z 14 to E 14 ?
S e c t i o n 9 . 2 Coding theory
introduction
We talked about cryptographic codes (codes for secrecy) in Chapter 5. The codes
we will talk about in this section are designed not to keep data secret but to cope
with degraded data. Data can degrade over time in a storage device or can be
corrupted over space, that is, during a transmission from one site to another over
some medium. Bits are changed from 0 to 1 or vice versa through interference
(“noise”), hardware failures, media damage, and so forth. The goal is to be able to
detect, perhaps even to correct, such errors.
Modeling Arithmetic, Computation, and Languages
“power” of 1, and 3Z, + 4 is cyclic with generator 1. Prove that the group 3Z 7 , + 7 4 is cyclic with
generator 2.
c. Prove that 5 is also a generator of the cyclic group 3Z 7 , + 7 4.
d. Prove that 3 is a generator of the cyclic group 3Z 4 , + 4 4.
42. Let 3G, # 4 be a cyclic group with generator a (see Exercise 41). Show that G is commutative.
43. a. Let 3S, # 4 be a semigroup. An isomorphism from S to S is called an automorphism on S. Let Aut(S) be
the set of all automorphisms on S, and prove that Aut(S) is a group under function composition.
b. For the group 3Z 4 , + 4 4, find the set of automorphisms and show its group table under + .
44. Let 3G, # 4 be a commutative group with identity i. Prove that the function f: G S G given by f (x) = x
−1
is an isomorphism.
45. Let f be a homomorphism from a group G onto a group H. Show that f is an isomorphism if and only if
the only element of G that is mapped to the identity of H is the identity of G.
46. Let 3G, # 4 be a group and g a fixed element of G. Define f: G S G by f(x) = g # x # g
−1
for any x [ G.
Prove that f is an isomorphism from G to G.
47. a. Consider the equivalence relation on the integers of congruence modulo n defined in Section 5.1. If
n = 5, there are 5 equivalence classes:
304 = 5… , −10, −5, 0, 5, 10, …6
314 = 5… , −9, −4, 1, 6, 11, …6
324 = 5… , −8, −3, 2, 7, 12, …6
334 = 5… , −7, −2, 3, 8, 13, …6
344 = 5… , −6, −1 ,4, 9, 14, …6
Let E 5 = 5 30 4, 314, 324, 33 4, 34 4 6. An operation + is defined on E 5 by
3x 4 + 3y 4 = 3x + y 4
For example, 324 + 344 = 32 + 4 4 = 36 4 = 31 4 (recall that an equivalence class can be named by any
of its elements). Prove that 3E 5 , + 4 is a commutative group.
b. 3Z 5 , + 5 4 is a commutative group with elements 50, 1, 2, 3, 46 (see Example 7). Prove that 3Z 5 , + 5 4 is
isomorphic to the group 3E 5 , + 4.
c. Results a and b hold for any value of n. In the group E 14 , what is the inverse of [10]? What is the preimage of [21] under the isomorphism from Z 14 to E 14 ?
S e c t i o n 9 . 2 Coding theory
introduction
We talked about cryptographic codes (codes for secrecy) in Chapter 5. The codes
we will talk about in this section are designed not to keep data secret but to cope
with degraded data. Data can degrade over time in a storage device or can be
corrupted over space, that is, during a transmission from one site to another over
some medium. Bits are changed from 0 to 1 or vice versa through interference
(“noise”), hardware failures, media damage, and so forth. The goal is to be able to
detect, perhaps even to correct, such errors.