Lagrange's Theory of Finite Groups states that any group
can only be divided up into subgroups of the same size.
EulerFermat's Theorem is an application of this, that says that any
number (coprime to n), rasied to a special power (called the totient
of n) will give 1 mod n.
The coprime and totient properties of the second theory are a
consequence of the structure of the Multiplicative Group of Integers Modulo n.
Let's use our Multiplicative Group of Integers Modulo 10 as an example to make this all a little clearer. This Group has four elements {1,3,7,9} and the operation is multiplication. Thus any element raised to the power of four, will give us 1.
$ 1^4$ is pretty obvious. It will always give us 1.
$ 3^4 = 81 = 1 \text{ mod } 10$
$ 7^4 = 2401 \text{ mod }10$
$ 9^4 = 6561 \text{ mod }10$
Now this is fascinating, but it was also the bit that was giving me headaches. Why does this always occur?
It turns out it's due to the basic properties of Finite Groups, specifically that each element a, has one inverse element a^{1}.
Let's bring back the multiplicative table of our example Group.
$\cdot $

1

3

7

9

1

1

3

7

9

3

3

9

1

7

7

7

1

9

3

9

9

7

3

1

If we look at the middle two columns,
if we start with a^{0} = 1 (our identity) and multiply
constantly by the same number, we end up with cycles that repeat
after four steps.
1 → 3 → 9 → 7 →
1 →
and
1 → 7 → 9 → 3 →
1 →
In these columns, we've looped through
the entire
Group. The largest
loop we can have in a group equals the number of elements we have in
that group.
The first column is much more trivial.
It will repeat itself after just 1 step.
1 → 1 → 1 → 1 →
1 →
But it's the last column that is most
interesting. Firstly, if we start from 1, we get a cycle that repeats
after two steps.
1 → 9 → 1 → 9 →
1 →
So we've got cycles of 1, 2 and 4. Why
not a cycle of 3?
Back to the last column, except we
start from 7, and multiply continually by 9.
7 → 3 → 7 → 3 →
7 →
So we've got two
cycles of two
in the last column. $2
\times 2 = 4$.
It
becomes clear when you consider what the 4^{th}
(Inverse) Group Law says about this type of cycle.
Firstly,
because there can only be one inverse for each element, then when we
constantly multiply by the same number (m), each element's behaviour
has
to look like this:
$m^{1}
\cdot a → a → m \cdot a$
And
this means that we can only have simple
cycles without branching or converging.
Which
also
means
that if you get two or more cycles,
they can't have any common elements. (This would represent a branch or convergence.)
Now
let's look at the cycles that start with 1. From the 2^{nd}
(Associative) Group Law, we can map this “identity” cycle to any
other element in the Group, to find new cycles that have the same
length. All
we have to do is multiply each value in the cycle by whatever we want
our new cycle to start with.
7
→ 3 → 7 → 3 → equals $7 \times 1 → 3 \times 7 \times 1 →
3^2 \times 7 \times 1$.
Because
we can multiply the identity element by any number to get a new
starting value, we can keep mapping the identity cycle to other
elements to get a new cycle of the same length.
Thus, once we have the identity cycle, we can keep mapping it to all
the elements in the group until
we have filled the
group up
with cycles, all the same length.
But
if all cycles are the same length, then cycle length $\times$ no.
cycles must equal the number of elements in the group #G.
Thus
cycle length must be a factor of #G, and if we step through #G times,
we are guaranteed
to end up at our starting position.
In
the first column, we reach our starting position in one
step,
but if we keep stepping four times, we will just complete the loop
four times.
In
the last column, we finish a cycle in two steps, and after four,
we've looped twice.
In
the middle columns, we need the whole four steps to complete one
cycle.
So,
in summary, loop sizes must be a factor of group size #G, and if we
step #G times, we may complete the cycle several times, but we will
always end up back at the start.
If
we start from 1,
then for each multiplication of m, we are calculating successive
powers of m. By the time we end up with $m^{\#G}$, we will be back at
the start, which is 1, proving
the
EulerFermat Theorem.
Since
this explanation depends not on multiplication, but rather
application of successive group operations and the existence of
cycles, it should be apparent that it applies to any Group – giving
us Lagrange's Theorem of Finite Groups.
No comments:
Post a Comment