RE: Cryptography 101 (An Interactive Class) : An Introduction to Group Theory - Week 1
Here are a two exercises.
Show that the set of even integers is a group.
Another group is a permutation group, also known as a symmetric group on n elements, denoted as
S_n. This group permutes the elements in a list to some different order. Symmetric groups are important because it turns out that ALL groups can be realized as the subgroup of a symmetric group. This result is known as Cayley's Theorem. An example of a symmetric group isS_3. Consider the natural ordering of a list as {1, 2, 3}. Now, we want to know how we can re-arrange this list. We can have {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, and {3, 2, 1}. How do we go from {1, 2, 3} to {1, 3, 2} ? We permute the elements 2 and 3 in the ordered list. This permutation is denoted as (2 3). Notation-wise, we start from the right and say that 3 goes to 2 and then 2 wraps back to the beginning of 3. The group operation is taken as performing permutations in order starting from right to left. That is to say with (1 2)(1 3)(1 2)(2 3), we see that 3 goes to 2 in the right most permutation, and then 2 goes to 1, and then 1 goes back to 3. So 3 stays fixed. Similarly, 2 goes to 3 which goes to 1 which goes to 2. And so 2 stays fixed. Since we have only 3 elements, and 2 of them are fixed, the third also must be fixed. So (1 2)(1 3)(1 2)(2 3) is actually the identity permutation (written in a more complicated form). We denote the identity of any symmetric group as (1), and we see that the identity never permutes any of the elements. Question: what group permutation element moves {1, 2, 3} to {3, 2, 1} ?
The set of even integers is an additive group. The identity is 0, since 0 + g = g for any integer g (even or otherwise). Addition is associative: if g1, g2, and g3 are even integers, then (g1 + g2) + g3 = g1 + (g2 + g3). Given an even integer g, its inverse is just -g. g + (-g) = 0. These seem pretty obvious. There's nothing else we need to say to show associativity and inverses, right?
For closure, suppose you've got two even integers, g1 and g2. Since they're even, you can factor out a 2 from each: g1 = 2m and g2 = 2 for some integers m and n. So, g1 + g2 = 2m + 2n = 2(m + n), and m + n is the sum of two integers, so it is also an integer, meaning the sum is an even integer.
The group permutation that moves {1, 2, 3} to {3, 2, 1} is (1 3).
1) Associativity can be taken from the integers, since we know the integers are associative, a subset of them will be as well. Inverses we do not automatically obtain, but it is obvious that if g = 2k in 2Z, for k in Z, then -g = -2k is also in 2Z. But, we need to explicitly state that and verify that it's the case.
Closure is done correctly. Good job!
2) Correct.
95/100, since you didn't explicitly state how the inverse of an even integer is also even.Oh, ok. Thanks