# Natural-number congruence modulo a positive modulus

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

For a fixed positive modulus n, two natural numbers a and b are congruent modulo n when they have the same remainder on division by n.

mko-modular-congruence · definition · v0.10.0



## 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

[Congruence modulo a positive modulus: the remainder definition, the witness form, preservation by operations and the limits of cancellation](https://ocme.evemisslab.com/en/derivations/derivation-mko-modular-congruence-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Natural number](https://ocme.evemisslab.com/en/mko/mko-natural-number/) — Inputs, modulus and remainders belong to the natural numbers.
- [Arithmetic operations](https://ocme.evemisslab.com/en/mko/mko-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.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/modular-congruence.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-modular-congruence/index.md)