# Question 339: A Modular Inverse Exists Exactly for a Unit

[Return to catalogue page 2](https://ocme.evemisslab.com/en/questions/page/2/)

[← Question derivation index](https://ocme.evemisslab.com/en/questions/) · [Original question batch](https://ocme.evemisslab.com/en/practice/batch-20261014-advance-20261103-r07-modular-inverse-foundations/#q-20261014-advance-20261103-r07-modular-inverse-0014)

This teaching derivation has second-context AI mathematical and bilingual semantic review, limited to the model and assumptions stated in this question. It has no human review or new Lean proof and does not promote the original question or MKO to Canonical truth.

P1000-0339 · q-20261014-advance-20261103-r07-modular-inverse-0014



## Original question and givens

Use the original signed integer a=3 and modulus n=40≥2. Exact extended Euclid gives nonnegative g=gcd(a,n) and signed coefficients x,y satisfying a*x+n*y=g. An inverse exists exactly when g=1; normalize its representative to 0≤inverse<n. Uniqueness means one residue class modulo n, not a unique integer representative. This family excludes moduli 0 and 1 and does not use approximate division. Give (a,n,gcd,exists?,inverse), with inverse=null for a nonunit.


- G001 — Use the original signed integer a=3 and modulus n=40≥2. Exact extended Euclid gives nonnegative g=gcd(a,n) and signed coefficients x,y satisfying a*x+n*y=g. An inverse exists exactly when g=1; normalize its representative to 0≤inverse<n. Uniqueness means one residue class modulo n, not a unique integer representative. This family excludes moduli 0 and 1 and does not use approximate division. Give (a,n,gcd,exists?,inverse), with inverse=null for a nonunit.





## Definition and scope

Integer a and modulus n≥2. An inverse exists exactly when gcd(a,n)=1; normalize the representative into [0,n).


- [mko-modular-inverse](https://ocme.evemisslab.com/en/mko/mko-modular-inverse/)





## Step-by-step derivation

S001 · impliesBefore

a=3; n=40≥2

After

compute gcd and a Bezout certificate before inversion

Conditions: none

Invertibility requires coprimality, after qualifying the modulus.

Step identifiers and dependenciesRule: modular_domain · Uses: G001





S002 · impliesBefore

divide 3 by 40

After

3=0·40+3

Conditions: none

Continue with divisor and remainder; nonzero remainders decrease strictly.

Step identifiers and dependenciesRule: euclidean_division · Uses: G001, S001





S003 · impliesBefore

divide 40 by 3

After

40=13·3+1

Conditions: none

Continue with divisor and remainder; nonzero remainders decrease strictly.

Step identifiers and dependenciesRule: euclidean_division · Uses: G001, S002





S004 · impliesBefore

divide 3 by 1

After

3=3·1+0

Conditions: none

Continue with divisor and remainder; nonzero remainders decrease strictly.

Step identifiers and dependenciesRule: euclidean_division · Uses: G001, S003





S005 · calculationBefore

a·x := mul(3, -13)

After

a·x = -39

Conditions: none

Multiply by the original signed a.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S004





S006 · calculationBefore

n·y := mul(40, 1)

After

n·y = 40

Conditions: none

Retain the modulus coefficient as well.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S005





S007 · calculationBefore

Bezout value := sum(-39, 40)

After

Bezout value = 1

Conditions: none

The two terms must sum to the final nonzero remainder, the gcd.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S006





S008 · impliesBefore

3·(-13)+40·(1)=1

After

inverse representative=27; 3·27≡1 (mod 40)

Conditions: none

Modulo n the modulus term vanishes; normalize the coefficient of a into[0,n).

Step identifiers and dependenciesRule: reduce_bezout · Uses: G001, S007









## Reverse checks


- S008 · premise_and_result_audit — Check integer identities, remainder bounds and gcd conditions; congruence is not integer equality.
- S007 · premise_and_result_audit — Recompute Bezout value with exact rational arithmetic, not rounded decimals.
- S006 · premise_and_result_audit — Recompute n·y with exact rational arithmetic, not rounded decimals.
- S005 · premise_and_result_audit — Recompute a·x with exact rational arithmetic, not rounded decimals.
- S004 · premise_and_result_audit — Check integer identities, remainder bounds and gcd conditions; congruence is not integer equality.
- S003 · premise_and_result_audit — Check integer identities, remainder bounds and gcd conditions; congruence is not integer equality.
- S002 · premise_and_result_audit — Check integer identities, remainder bounds and gcd conditions; congruence is not integer equality.
- S001 · premise_and_result_audit — Check integer identities, remainder bounds and gcd conditions; congruence is not integer equality.





## Result

(3, 40, 1, Yes, 27)

The full substitutions and premise audits recover the original answer, retaining its field order and verdict meanings.





## This question review and source binding

Review date: 2026-10-26

Original questions, answers, step expressions, numeric ASTs and historical records are retained. Source candidate labels remain historical and are not overwritten as formal proof.

Source hashes and review receipts
- input commit: 0f7be61e2c22317a4075561dc822c87d881a50db
- original question SHA-256: 05857d6ed89954a69fff02fec77931b33a5eade41b602c794225f239aec75797
- candidate record SHA-256: a1fc7dcd0644599534ab185b56f7ec7e7cc0b1052d9a0c0bf4e6fdd1ed0322d7
- semantic review receipt SHA-256: 6c2c6d46aded7582a11ac41a8c0b3bdde2669a53bdb6e796eea2039994a02772
- question-first witness SHA-256: 77e43898df9efdbf8094ad81fe4ab91cf4b4bd82f481eb9b4699b73cb4da612b
- Lean: NOT_RUN · human review: NOT_PERFORMED

[Same-source full JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261014-advance-20261103-r07-modular-inverse-0014.json)