Natural-number congruence modulo a positive modulus

Mathematical statement

For natural numbers a,b and a positive natural n, a≡b (mod n) exactly when a mod n=b mod n. Equivalently, there are natural k,l with a+n·k=b+n·l.

Representative formula (exact TeX)

r(a)=r(b)

Assumptions

• The inputs a and b are natural numbers and the modulus n is a positive natural number.
• This entry deliberately excludes n=0 so that programming-language mod-zero conventions are not mixed with ordinary elementary-number-theory semantics.

Symbol scope

• r — remainder function for a fixed positive modulus
• a — first natural-number input
• b — second natural-number input

Intuition, definition, and misconceptions

Congruence compares remainders under the same fixed modulus, not numerical equality. It is an equivalence relation on the natural numbers.

If a≡b (mod n) and c≡d (mod n), addition and multiplication preserve congruence. Finite exercises recompute the remainders explicitly.

Cancelling a multiplicative factor requires extra conditions. One cannot generally cancel c from c·a≡c·b without considering the gcd of c and n.

Do not mix moduli, admit a zero modulus in this entry, or cancel common factors unconditionally.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Natural number — Inputs, modulus and remainders belong to the natural numbers.
• Arithmetic operations — Congruence calculations use exact division remainders, addition and multiplication.

Verification boundary

Finite remainders for a fixed positive modulus can be checked exactly; this slice does not claim a formal Chinese remainder theorem or general cancellation law.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Bind the remainder definition of Nat.ModEq, its equivalence relation and add/mul preservation; separately prove the symmetric natural-witness bridge.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.