Skip to content
Axiomatic Wiki

WTThe integers modulo n have exactly n elements

Theorem·T60

There are exactly n residue classes modulo a positive n.

For , , so is finite with (D035, D033).
In words
For a positive modulus n, the integers modulo n are in bijection with the numbers 0 through n minus 1, so there are exactly n residue classes.
Rests onF02F03F04F05F06F08F09F11F12F13F14A01A02A06A08
Never needed: F10 · A03 · A04 · A05 · A07 · A09 (computed from the citation graph, not asserted).

Proof

  1. 1
    The natural number is the set of naturals below it (D029). Define by for (a function by Separation, each having one class). We show is a bijection.
  2. 2
    Injective. Let with ; by trichotomy assume (the case is symmetric). Then , so (L73, T04); by D113 this gives for some .
  3. 3
    Since , the gap lies in with (L47, L46). So is an integer multiple of , hence in (L76). If then (L19 (vii)); but (L17 (i), ), so is a contradiction. Hence and .
  4. 4
    Surjective. Any is for some (D114, D022). By L77, with , , . Then (T23), an integer multiple of , so (D113); thus (L73, T04). Since means (D029), is a value of .
  5. 5
    So is a bijection , giving (D033). As , is finite, and since and the cardinality is the unique such natural (D035, L23).
∎

Remarks

The sets are a complete residue system: every integer is congruent to exactly one of them, its remainder under division by . This is the count that makes a finite ring, so Lagrange-style counting and L36 apply to its group of units, the route to Euler and Fermat. For the quotient is infinite (a copy of ), which is why is required.
Wikipedia ↗ZMod.card ↗

Used by

L80T61
Propose an edit1 published revision