Eulers Theorem

2021 Apr 15 See all posts

This is euler's theorem (for coprime n and k)

kϕ(n)1(modn)k^{\phi(n)} \equiv 1 \pmod n

Key fact

The integers coprime to n, mod n forms a group. since multiplication by kk is invertible (since k is coprime to n, and k is in the group). Multiplying each element by kk just reorders the elements.

Example: multiply each coprime number by 33 mod 88 (Remember mod is the same as the remainder from divison)

(13)=33(33)=91(53)=157(73)=215\begin{aligned} (1 \cdot 3) &= 3 &\to 3 \\ (3 \cdot 3) &= 9 &\to 1 \\ (5 \cdot 3) &= 15 &\to 7 \\ (7 \cdot 3) &= 21 &\to 5 \end{aligned}

And the product is the same if each element is multiplied by 33, since we take out as many 88's as we can from each term.

1357(31)(33)(35)(37)3175(mod8)1 \cdot 3 \cdot 5 \cdot 7 \equiv (3 \cdot 1) (3 \cdot 3) (3 \cdot 5) (3 \cdot 7) \equiv 3 \cdot 1 \cdot 7 \cdot 5 \pmod 8

The Proof

If we have {k1,,kϕ(n)}\{k_1, \dots, k_{\phi(n)}\} being the integers coprime to n.

We know kk is in the set (since n and k are coprime). if we multiply each kik_i by kk we have

ϕ(n)kiϕ(n)kik(modn)\prod^{\phi(n)} k_i \equiv \prod^{\phi(n)} k_i k \pmod n

Because of invertibility (no overlaps/no duplicates) and closure (stays in the set of coprimes), multiplying each kik_i by kk just reorders the elements.

Now we factor out k and invert/divide by the product (which will just be another k)

1ϕ(n)kikϕ(n)ϕ(n)ki(modn)1 \cdot \bcancel{\prod^{\phi(n)} k_i} \equiv k^{\phi(n)} \bcancel{\prod^{\phi(n)} k_i} \pmod n

So we end up with

kϕ(n)1(modn)k^{\phi(n)} \equiv 1 \pmod n

Proof it is a group

There are 4 group axioms we must satisfy

  1. Closure: if k1k_1 and k2k_2 share no factors with nn, k1k2k_1 k_2 share no factors with nn.
  2. An identity element: just 11 in our case
  3. Associativity: multiplication is associative
  4. Invertibility: see below

Let kk be an element of the group, we know that gcd(k,n)=1\gcd(k, n) = 1 (coprime)

Euclids algorithm implies there exist ss and tt such that

sk+tn=1sk + tn = 1

(Also known as Bézout's identity)

Now mod out by nn

sk+tn=1    sk1(modn)sk + tn = 1 \implies sk \equiv 1 \pmod n

Therefor s=k1s = k^{-1}, and an inverse exists!