Chinese remainder theorem

Mathematical statement

Normalize residues, construct a simultaneous solution using modular-inverse methods and check every congruence. Uniqueness is modulo the product, not uniqueness as an integer. Modulus zero is invalid. A noncoprime system is outside the main hypothesis but may be compatible; test pairwise gcd conditions and use the lcm period in general.

Representative formula (exact TeX)

C(R)

Assumptions

• The main CRT questions use positive pairwise-coprime moduli.
• All integer arithmetic is exact.

Symbol scope

• C — CRT solution
• R — residue system

Intuition, definition, and misconceptions

Construct a normalized simultaneous solution.

Check every congruence.

Noncoprime systems need compatibility checks and are not automatically inconsistent.

Unique modulo the product does not mean a unique integer, and noncoprimality alone does not imply inconsistency.

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

• Integer — Solutions and residues are integers.
• Natural-number congruence modulo a positive modulus — Each system equation is a congruence.
• Greatest common divisor and coprimality — The main hypothesis is pairwise coprimality.
• Quantifiers and explicit domains — Every equation and the residue-class uniqueness obligation must hold.

Verification boundary

Keep the pairwise-coprime theorem separate from noncoprime boundary audits.

not_formalized

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

Next obligation

Add the generalized Chinese remainder theorem.

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.