Skip to content
Axiomatic Wiki

WLThe totient of a prime

Lemma·L80

For a prime p, exactly the p minus 1 nonzero residue classes are units, so the totient is p minus 1.

For (D031), that is, equals : every nonzero residue class modulo is a unit. ( from D118.)
In words
For a prime p, the totient of p is one less than p: every one of the p minus 1 nonzero residue classes is invertible.
Rests onF02F03F04F05F06F08F09F11F12F13F14A01A02A06A08
Never needed: F10 · A03 · A04 · A05 · A07 · A09 (computed from the citation graph, not asserted).

Proof

  1. 1
    prime gives , so and has exactly elements (T60). Write .
  2. 2
    is not a unit. If then (D113), forcing (L19 (vii)), against ; so . For any class , (as , L45 (i), D116), which is , so (D117).
  3. 3
    Every nonzero class is a unit. Let with . By T60 its bijection, for some with ; as , , so . Now (T19, ) divides , so or (D031, D055); would give , impossible for (L19 (vii)). So and (L78).
  4. 4
    Count. By the last two steps , a disjoint union. Both are finite ( by T61, and by D035), so L26 gives (D118). Since , we get .
∎

Remarks

A prime modulus is special: since a prime's only divisors are and itself, every residue with is coprime to , so its class is a unit. Only is left out, giving . Equivalently, is a field: every nonzero element is invertible. This is the count that turns Euler's theorem into Fermat's little theorem.
Wikipedia ↗Nat.totient_prime ↗

Used by

T63
Propose an edit1 published revision