2021 Apr 15
See all posts
This is euler's theorem (for coprime n and k)
The integers coprime to n, mod n forms a group.
since multiplication by is invertible (since k is coprime to n, and k is in the 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.
If we have being the integers coprime to n.
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!