Skip to content
Axiomatic Wiki

WLA residue class is a unit exactly when its representative is coprime to n

Lemma·L78

A residue class is invertible modulo n exactly when its representative is coprime to n.

For with : units from D117, from D055.
In words
The class of a is a unit modulo n exactly when a and n are coprime: they share no common factor beyond 1.
Rests onF02F03F04F05F06F08F09F11F12F13F14A01A02A06A08
Never needed: F10 · A03 · A04 · A05 · A07 · A09 (computed from the citation graph, not asserted).

Proof

  1. 1
    Coprime implies unit. Suppose . As , the pair is not both , so T25 gives with .
  2. 2
    Then (L45 (ii)), an integer multiple of , so (D113). Passing to classes, (D116; congruent representatives give the same class, L73, T04), so is an inverse and (D117).
  3. 3
    Unit implies coprime. Suppose for some (D117). Then (D116), so (L73, T04), that is , equivalently , for some (D113).
  4. 4
    Let (T19, well posed since are not both ). Then and (D055), say and ; applying , and (L46).
  5. 5
    Substituting and factoring with distributivity (T23): So is an integer multiple of , whence in (L76). Since , L19 (vii) gives ; and (else ), so : .
∎

Remarks

This identifies with the classes of residues coprime to , the bridge between the ring structure and number theory. The forward direction is the source of modular inverses: the extended Euclidean algorithm computes the inverse . When is prime, every with satisfies (a prime's only divisors are and , D031), so every nonzero class is a unit, which is exactly why is a field. Counting the coprime residues gives Euler's totient .
Wikipedia ↗ZMod.isUnit_iff_coprime ↗

Used by

L80T62
Propose an edit1 published revision