Eulers Theorem

Added 2021-04-15, Modified 2022-09-18

Groups make it easy

Update: This is all a trivial consequence of Lagrange's Theorem on finite groups implying groups of prime order are all the cyclic group. See this video for a great explanation.

Eulers theorem: If ϕ(n)\phi(n) is the number of integers coprime to nn, and kk is any integer coprime to nn we have

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

Key fact

The integers coprime to n, mod n forms a group (generally denoted (Z/nZ)×(\mathbb{Z}/n\mathbb{Z})^{\times}). Since multiplication by kk is invertible (because it's a 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

Let {k1,,kϕ(n)}\{k_1, \dots, k_{\phi(n)}\} be the integers coprime to nn and let kk be coprime to nn.

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!

General case (Group Theory)

Looking back on this proof, the only facts we needed were that (Z/nZ)×(\mathbb{Z}/n\mathbb{Z})^{\times} is a finite group, and that multiplication is communicative (needed when we factored out kϕ(n)k^{\phi(n)}). Since those are the only dependencies, it must be true for all finite communicative groups!

An example is the additive group of integers modulo nn denoted (Z/nZ)+(\mathbb{Z}/n\mathbb{Z})^+, in this case Group multiplication becomes Group addition, the identity element becomes 00 and xnx^n now denotes repeated addition so xn=nxx^n = nx.

Our theorem says that xn=1x^n = 1 for all xx in the group, where nn is the size of the group. In the addition case this becomes nx=0(modn)nx = 0 \pmod n which can be seen directly as nxnx is divisible by nn.