Eulers theorem: If is the number of integers coprime to , and is any integer coprime to we have
The integers coprime to n, mod n forms a group (generally denoted ). Since multiplication by is invertible (because it's a group) multiplying each element by just reorders the elements.
Example: multiply each coprime number by mod (Remember mod is the same as the remainder from divison)
And the product is the same if each element is multiplied by , since we take out as many 's as we can from each term.
Let be the integers coprime to and let be coprime to .
We know is in the set (since n and k are coprime). if we multiply each by we have
Because of invertibility (no overlaps/no duplicates) and closure (stays in the set of coprimes), multiplying each by just reorders the elements.
Now we factor out k and invert/divide by the product (which will just be another k)
So we end up with
Proof it is a group
There are 4 group axioms we must satisfy
- Closure: if and share no factors with , share no factors with .
- An identity element: just in our case
- Associativity: multiplication is associative
- Invertibility: see below
Let be an element of the group, we know that (coprime)
Euclids algorithm implies there exist and such that
(Also known as Bézout's identity)
Now mod out by
Therefor , and an inverse exists!
General case (Group Theory)
Looking back on this proof, the only facts we needed were that is a finite group, and that multiplication is communicative (needed when we factored out ). Since those are the only dependencies, it must be true for all finite communicative groups!
An example is the additive group of integers modulo denoted , in this case Group multiplication becomes Group addition, the identity element becomes and now denotes repeated addition so .
Our theorem says that for all in the group, where is the size of the group. In the addition case this becomes which can be seen directly as is divisible by .