Modular inverse

Mathematical statement

Use extended Euclid for an exact Bezout certificate a*x+n*y=1 and return the normalized representative 0≤x mod n<n. Modulus zero is invalid, and this slice requires n≥2. A nonunit explicitly has no inverse; approximate division is not used.

Representative formula (exact TeX)

I(a)

Assumptions

• a is an integer and n≥2 is the modulus.
• Congruence and gcd calculations use exact integer arithmetic.

Symbol scope

• I — modular inverse
• a — integer representative

Intuition, definition, and misconceptions

gcd(a,n)=1 is equivalent to inverse existence.

Extended Euclid supplies a Bezout witness.

Return a normalized residue; a nonunit has no inverse.

Do not divide by a nonunit or use modulus zero, and do not confuse a unique residue class with a unique integer representative.

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

• Greatest common divisor and coprimality — The gcd condition and Bezout identity characterize existence.
• Natural-number congruence modulo a positive modulus — Uniqueness is only up to a residue class.
• Equation — The certificate satisfies a*x+n*y=1.

Verification boundary

This slice requires n≥2 and does not adopt a degenerate n=1 convention.

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 Chinese remainder theorem and modular linear equations.

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.