# Question 374: Keep Signed Bezout Coefficients and Verify the Integer Identity

[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-0049)

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-0374 · q-20261014-advance-20261103-r07-modular-inverse-0049



## Original question and givens

Use the original signed integer a=3 and modulus n=50≥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,x,y,bezout_value,classification), retaining the coefficients returned by exact Euclidean steps on |a| and n, with the sign of a restored in x.


- G001 — Use the original signed integer a=3 and modulus n=50≥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,x,y,bezout_value,classification), retaining the coefficients returned by exact Euclidean steps on |a| and n, with the sign of a restored in x.





## Definition and scope

Run extended Euclid on |a| and n and restore the sign of a. The coefficients are one Bezout witness, not a unique pair.


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





## Step-by-step derivation

S001 · impliesBefore

a=3; n=50≥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 50

After

3=0·50+3

Conditions: none

Continue with divisor and remainder; nonzero remainders decrease strictly.

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





S003 · impliesBefore

divide 50 by 3

After

50=16·3+2

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 2

After

3=1·2+1

Conditions: none

Continue with divisor and remainder; nonzero remainders decrease strictly.

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





S005 · impliesBefore

divide 2 by 1

After

2=2·1+0

Conditions: none

Continue with divisor and remainder; nonzero remainders decrease strictly.

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





S006 · calculationBefore

a·x := mul(3, 17)

After

a·x = 51

Conditions: none

Multiply by the original signed a.

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





S007 · calculationBefore

n·y := mul(50, -1)

After

n·y = -50

Conditions: none

Retain the modulus coefficient as well.

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





S008 · calculationBefore

Bezout value := sum(51, -50)

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, S007





S009 · impliesBefore

3·(17)+50·(-1)=1

After

inverse representative=17; 3·17≡1 (mod 50)

Conditions: none

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

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









## Reverse checks


- S009 · premise_and_result_audit — Check integer identities, remainder bounds and gcd conditions; congruence is not integer equality.
- S008 · premise_and_result_audit — Recompute Bezout value with exact rational arithmetic, not rounded decimals.
- S007 · premise_and_result_audit — Recompute n·y with exact rational arithmetic, not rounded decimals.
- S006 · premise_and_result_audit — Recompute a·x with exact rational arithmetic, not rounded decimals.
- S005 · premise_and_result_audit — Check integer identities, remainder bounds and gcd conditions; congruence is not integer equality.
- 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, 50, 1, 17, -1, 1, Bezout_equals_one)

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: 96f67ddb30c063eea29a173f6ac036af4b697540a2b1a5787a95b9c968518895
- candidate record SHA-256: c94da183682126f30a176b240d318051a00dff255e380d459ce304914ec56b7d
- 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-0049.json)