Skip to content
Axiomatic Wiki

WLCongruence is compatible with addition and multiplication

Lemma·L74

Replacing the inputs by congruent ones does not change the congruence class of a sum or product.

Fix . If and (D113), then and , for all .
In words
If a may be replaced by a congruent a-prime and b by a congruent b-prime, modulo n, then the sum a plus b is congruent to a-prime plus b-prime and the product a times b is congruent to a-prime times b-prime, modulo n.
Rests onF02F03F04F05F06F08F09F11F12F13F14A01A02A06A08
Never needed: F10 · A03 · A04 · A05 · A07 · A09 (computed from the citation graph, not asserted).

Proof

  1. 1
    By hypothesis and D113, and for some .
  2. 2
    Sums. In the abelian group (T22), (regroup and use ). This equals by distributivity (T23), an integer multiple of , so (D113).
  3. 3
    Products. Inserting a middle term and using distributivity with the sign rule L45 (ii) in the ring (T23):
  4. 4
    Substituting and and using associativity and commutativity of (T23): an integer multiple of , so (D113).
∎

Remarks

This is what makes modular arithmetic arithmetic: the congruence class of a sum or product depends only on the classes of the inputs, never on the chosen representatives. It is exactly the well-definedness needed for the operations addition and multiplication on , and it says the quotient map preserves and . Concretely one may reduce intermediate results modulo at any point: to compute modulo , replace and by their remainders first.
Wikipedia ↗Int.ModEq.add ↗

Used by

T59T63
Propose an edit1 published revision