GROUP THEORY

MATH 195

The reference for the material covered here is any abstract algebra book; the text by Fraleigh, A First Course in Abstract Algebra, sixth edition, is often used at Berkeley.

Group theory

Definition. A group is a set G together with a map ∗ : G × G → G such that: • (a ∗ b) ∗ c = a ∗ (b ∗ c) for all a, b, c ∈ G;

• There exists an e ∈ G such that for all a ∈ G, e ∗ a = a ∗ e = a;

• For all a ∈ G, there exists an a′ ∈ G such that a ∗ a′ = a′ ∗ a = e.

If you have never seen groups before and want some practice (or examples), check out SS1.1–1.3 in Fraleigh.

Given an element b ∗ a, we can recover b by multiplying by a′:

(b ∗ a) ∗ a′ = b ∗ (a ∗ a′) = b ∗ e = b.

Notice how this looks like “decryption”.

Many of our groups (but not all) will be abelian: a ∗ b = b ∗ a.

Example. The group of permutations on the (finite) set S, which we called G = Sym S, has ∗ = ∘ (the group law is composition), e = id_{S}, and f′ = f^{−1}. This group is nonabelian if S has more than 2 elements. (See §2.1 in Fraleigh.)

Here is notation which is often used for groups:

“Additive” group (usually abelian) “Multiplicative” group
∗ = +  ∗ = ∘, ×, , ·
a′ = −a  a′ = a^{−1}
e = 0  e = 1, id
multiple  power
n · a = na  a^{n}
0a = 0  a^{0} = 1
(−n)a = n(−a)  a^{−n} = (a^{−1})^{n}
(m + n)a = ma + na  a^{m+n} = a^{m}a^{n}
The Group (ℤ/nℤ)^{∗}

Notice that the set ℤ/26ℤ = {0, 1, 2, …, 25} with the addition law (taking the remainder modulo 26) is a group. However, using the multiplication law, it is not a group. Although it satisfies the associativity law and has an identity element 1, not every element has an inverse: for example 0 has no inverse. In fact, any element which is not relatively prime to 26—e.g. 12, since if 12a′ = 1 in ℤ/26ℤ, then 12a′ = 1 + 26n for some n ∈ ℤ, which is impossible as the left-hand side is even whereas the right hand side is odd.

This is some of the material covered January 29, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.

The set ℤ/nℤ = {0, 1, …, n − 1} is never a group unless n = 1, in which the group is just {0}. The set

ℤ/nℤ \ {0} = {1, 2, …, n − 1}

is a group when n is prime and not otherwise: it fails even to be closed—for example, 2 · 13 ≡ 0 (mod 26) is no longer in the group. In general, however, we may take the set of units

(ℤ/nℤ)^{∗} = {a ∈ ℤ/nℤ : gcd(a, n) = 1},

and this is a group under multiplication. (For this, see §5.3, especially Theorem 5.3.6 in Fraleigh. It is also covered in SS7.1–7.3 of our text, Stallings.)

Example. Since 26 = 2 · 13,

(ℤ/26ℤ)^{∗} = {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25},

a group with 12 elements. We have 7 · 11 ≡ 25 ≡ −1 (mod 26), and therefore 7^{−1} ≡ −11 ≡ 15 (mod 26).

In general, the number of elements of this multiplicative group is

#(ℤ/nℤ)^{∗} = n ∏_{p|n} (1 − \frac{1}{p}) .

Note that this agrees with the above enumeration, since 26(1/2)(12/13) = 12.