Saturday, 18 May 2013

Euler's Totient Function

As mentioned in the last post, when multiplying Integers mod n, there are some Integers that can't have an inverse. My example was, that it was impossible to multiply 2 by anything, that once divided by 10, gave you a remainder of 1. Likewise for 5. And if an element doesn't have an inverse with respect to some mathematical operation, then that element can't be a member of a Group.

So let's look at the numbers from 0 to 9 that obey the Group Laws under multiplication, modulo 10. Anything that breaks a Group Law will be eliminated from consideration, and we will investigate what is left over.

Firstly, all the numbers from 0 to 9, when multiplied mod 10, will give us a number from 0 to 9, so all the numbers are closed under multiplication so far. They obey the 1st (Closure) Group Law.
Secondly, multiplication is commutive, thus so is modular multiplication. 2nd (Associative) Group Law satisfied.
Thirdly, there is a number, that when multiplied by another, doesn't change the second number's value. That number is 1 ($1 \times a = a$ and $a \times 1 = a$) and here-on in, will be our identity. (3rd Group Law)

However, once we hit the 4th (Inverse) Group Law, we start having to eliminate numbers.
0 doesn't have a multiplicative inverse. There is nothing that we can multiply 0 by to get our identity element, 1. So now our Set only consists of the numbers from 1 to 9.
0 is now outside our Set and by the application of the 1st (Closure) Law, anything that can give us 0 mod 10, must also be removed. And that eliminates any number that is a factor of 10 (2 and 5).
It also eliminates any number that shares a factor of 10 (4, 6, 8), as we can always find a multiple ($4 \times 5 = 20$, $6 \times 5 = 30$) that will give us 0 when we mod by 10.

So our Group now only consists of the numbers {1, 3, 7, 9}, and the operator table (think times table) will look like:
 $\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

This group has a special name, the Multiplicative Group of Integers Modulo 10. We say that all the numbers of this Group are coprime (don't share any factors except 1) with 10, and the number of elements in it, (4 in this case) is called the Totient of 10.

This Set of numbers obey all the Group Laws, and thus, all the findings of Group Theory will apply, including Lagrange's Theory of Finite Groups.