Mathematics 243, section 1 – Algebraic Structures Review Sheet, Final Exam December 4, 2006

General Information

The final examination for this course will be given at 8:30 a.m. on Wednesday, December 13 in our regular class room, Swords 328. It will be a comprehensive exam, covering all the material we have studied each semester, divided roughly in thirds according to the topics from the three hour exams. Some questions on earlier material (e.g. the one-to-one and onto properties of mappings, binary operations, equivalence relations, etc.) may appear in the context of topics covered later in the semester, though. The exam will be roughly twice the length of one of the three midterms, but you will have the full three hour period from 8:30 am to 11:30 am to work on it if you need that much time.

Topics to be Covered

1) Sets: set operations (union, intersection, difference, complement, Cartesian product, etc.) and their properties.

2) Mappings: the 1-1 and onto properties, direct and inverse images of sets under mappings,

3) Binary operations: identity elements, inverses, properties such as associativity, commutativity, key examples such as function composition, matrix addition and multiplication, addition and multiplication in Z and Z_{n}, etc.

4) Relations: especially equivalence relations and the partition of a set into equivalence classes under an equivalence relation (key example: the congruence mod n relation on Z – the set of equivalence classes in that case is Z_{n}).

5) Properties of Z: the Well-Ordering Property, proof by mathematical induction, the division algorithm, divisibility, prime numbers and prime factorizations, the gcd and lcm of two integers, Euclid’s algorithm for the gcd.

6) The congruence mod n relation on Z and the integers modulo n, addition and multiplication in Z_{n} and their properties. Applications to cryptography (affine and RSA cryptosystems).

7) Groups: the definition, key examples such as Z_{n} under addition mod n, the group

U(n) = {[x] ∈ Z_{n} : [x]^{−1} (multiplicative inverse) exists} = {[x] ∈ Z_{n} : gcd(x, n) = 1}

under multiplication mod n, GL_{2}(R), the symmetric groups S_{n}, etc.

8) Subgroups of groups: know how to determine whether a given subset of a group is a subgroup. Cyclic subgroups.

9) Cyclic groups, generators, orders of elements, etc.

10) Homomorphisms of groups, kernel and image of a homomorphism, isomorphisms.

11) Permutation groups and cycle notation for permutations, orders of permutations.

Proofs to Know

See the review sheets for Exams 1, 2, and 3. (These are reposted on the course homepage in case you need additional copies.)

Suggestions on How to Study

Start by reading the above list of topics carefully. If there are terms there that are unfamiliar or for which you cannot give the precise definition, learn the definitions now. Review the class notes. Everything on the final will be similar to something we have discussed at some point this semester. Also look back over your graded problem sets and exams. If there are problems that you did not get the first time around, try them again now. Then go through the suggested problems from the three review sheets. If you have worked these out previously, it is not necessary to do them all again. But try a representative sample “from scratch” – don’t just look over your old solutions and nod your head if it looks familiar. You need the practice thinking through the logic of how the solution is derived again!

Review Session

I will be happy to run a review session for the final exam during study week. We can discuss a time in class on Monday, December 4.

Some Sample Exam Questions

I.

A) Let A = Z, the set of all integers. Consider φ : A → A be the mapping defined by

φ(x) = \{ \begin{matrix}5x & if x is even \\ x − 2 & if x is odd \end{matrix}

Is φ one-to-one? Why or why not? Is φ onto? Why or why not? B) What is φ^{−1}({3, 4, 5, 6, 7}) for the mapping in part A? C) What is φ({1, 2, 3} ∩ {x ∈ A : x^{2} < 5})?

II. A) Give the precise statement and the proof of the Division Algorithm in Z. B) Find the integer d = gcd(753, 154) and express d in the form d = 753m + 154n for

some integers m, n. C) Show that if a, b, c are integers, a|(b · c) and gcd(a, c) = 1, then a|b.

III. Let f_{0} = 0, f_{1} = 1, and f_{n} = f_{n−1} +f_{n−2} for all n ≥ 2. The f_{n} are called the Fibonacci numbers; the first few of them are 1, 1, 2, 3, 5, 8, 13, 21, 34, . . ..

A) Let A = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ). Compute the matrix powers A^{2}, A^{3}, A^{4}. Do you see a pattern

developing? B) (The pattern!) Show by mathematical induction:

( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )^{n} = ( \begin{matrix}f_{n+1} & f_{n} \\ f_{n} & f_{n−1} \end{matrix} )

for all n ≥ 1.

IV. A) In an affine cipher on a 26-letter alphabet, “E” (the most common letter) is encrypted

to “Z” and “T” (the next most common letter) is encrypted to “B”. What are the encryption and decryption functions?

B) In an RSA public key cryptosystem, the public key consists of the integer m = 323 and the encryption exponent e = 29. What is the decryption exponent d?

V. Consider the following set of all 2 × 2 matrices with real entries:

G = \{( \begin{matrix}a & b \\ 0 & d \end{matrix} ) | a, b, d ∈ R\} .

A) Show that G is a group under matrix addition. B) Is the set

H = \{( \begin{matrix}1 & n \\ 0 & 1 \end{matrix} ) | n ∈ Z\}

a subgroup of the group from part A? Why or why not?

VI. All parts of this question refer to Z_{30}, in which the operations are addition and multiplication mod 30. A) Which elements of Z_{30} have multiplicative inverses in Z_{30}? B) Find all the elements of the additive group (Z_{30}, +) that generate the additive sub-

group ⟨[24]⟩.

VII. Let G and H be groups and let φ : G → H be a group homomorphism. A) Give the precise definition of the kernel of φ, ker(φ). B) Show that if K = ker(φ) and g ∈ G is an arbitrary fixed element, then gKg^{−1} =

{gkg^{−1} | k ∈ K} is equal to K. C) Show that the relation R on G defined by

xRy ⇔ xy^{−1} ∈ ker(φ)

is an equivalence relation on G.

VIII. Are there any elements of order 14 in the symmetric group S_{8}? Why or why not?