SECTION 4.2 Basics of Group Theory 221
If any two of these elements are the same, say a′a = a′′a, for
distinct elementsa′anda′′, then (a′−a′′)a= 0. But this would
say thatp|(a′−a′′)a; sincepis prime, and sincep6|a, this implies
thatp|(a′−a′′). But 1≤a′, a′′< pand so this is impossible unless
a′ =a′′, contradicting our assumption that they were distinct in
the first place! Finally, since we now know that the elements in
the above list are all distinct, there are exactlyp−1 such elements,
which proves already that{ 1 ·a, 2 ·a, 3 ·a, ...,(p−1)·a} = Z∗p.In particular, it follows that 1∈{ 1 ·a, 2 ·a, 3 ·a, ...,(p−1)·a},
and soa′a= 1 for somea′∈Z∗p, proving thata′=a−^1. In short,
we have proved that (Z∗p,·) is a group.Themultiplication tablefor a (finite) group (G,∗) is just a table
listing all possible products.^9 We give the multiplication table for the
group (Z∗ 7 ,·) below:
· 1 2 3 4 5 6
1 1 2 3 4 5 6
2 2 4 6 1 3 5
3 3 6 2 5 1 4
4 4 1 5 2 6 3
5 5 3 1 6 4 2
6 6 5 4 3 2 1On the basis of the above table, we find, for instance that 4−^1 = 2 and
that 3−^1 = 5. Even more importantly, is this: if we letx= 3, we get
x^0 = 1, x^1 = 3, x^2 = 2, x^3 = 6, x^4 = 4, x^5 = 5, x^6 = 1,which says thatevery element of Z∗ 7 can be expressed as some
power of the single element 3. This is both important and more
(^9) The multiplication table for a group is often called theCayley tableafter the English mathe-
matician Arthur Cayley (1821–1895).