Skip to content
Axiomatic Wiki

WTEuler's theorem

Theorem·T62

A number coprime to n, raised to the totient of n, is congruent to 1 modulo n.

For with and (coprime), with Euler's totient and the power from D119.
In words
If a is coprime to n, then a raised to the totient of n is congruent to 1 modulo n.
Rests onF02F03F04F05F06F08F09F11F12F13F14A01A02A06A08
Never needed: F10 · A03 · A04 · A05 · A07 · A09 (computed from the citation graph, not asserted).

Proof

  1. 1
    Since , the class is a unit (L78), so it lies in the finite group (T61), whose order is (D118).
  2. 2
    By L36 applied to this finite group (an element raised to the group's order is the identity), , using the group power, with the identity.
  3. 3
    By L79, . Hence , that is (L73, T04: equal classes mean congruent representatives).
∎

Remarks

Euler's theorem (1763). The proof is pure group theory: the units modulo form a finite group of order (T61), and raising any element to the group order returns the identity (L36). This is exactly the specialization anticipated in the notes of L36. It generalizes Fermat's little theorem (the case prime, where ) and is the arithmetic behind RSA, where decryption works because whenever . Example: and , so .
Wikipedia ↗ZMod.pow_totient ↗

Used by

T63
Propose an edit1 published revision