Lagrange's Theory of Finite Groups and the Euler-Fermat Theorem.

In my Group Theory post, I stated that once a Set of mathematical elements and a mathematical operation have been proven to satisfy some basic properties, all theories, proofs and facts from the mathematical discipline of Group Theory, would automatically apply.

 Lagrange's Theory of Finite Groups states that any group can only be divided up into subgroups of the same size.

Euler-Fermat'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⁰ = 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 Euler-Fermat 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.

These two posts will show what this fact is useful for.