Question 61: Normalize the Inverse Representative, Not the Bezout Coefficients

Original question and givens

Use the original signed integer a=2 and modulus n=37≥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. Require gcd(a,n)=1. Give (a,n,inverse,product_mod_n,valid?,unique_modulo_n).

• G001 — Use the original signed integer a=2 and modulus n=37≥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. Require gcd(a,n)=1. Give (a,n,inverse,product_mod_n,valid?,unique_modulo_n).

Definition and scope

Use integer modulus n≥2 with gcd(a,n)=1. Uniqueness concerns the residue class and its representative in the declared interval.

• mko-modular-inverse

Step-by-step derivation

a=2, modulus=37

n=37≥2; seek u with 2u≡1 (mod 37)

divide 2 by 37

2=0·37+2

divide 37 by 2

37=18·2+1

divide 2 by 1

2=2·1+0

last nonzero Euclidean remainder

gcd(2,37)=1; 2·(-18)+37·(1)=1

2·(-18)+37·(1)=1

-18 mod 37=19; 0≤19<37

a·u := mul(2, 19)

a·u = 38

a·u=38

38=1·37+1 ⇒ a·u mod n=1

a·v≡a·u≡1 (mod n), gcd(a,n)=1

n divides v−u; if 0≤u,v<n then u=v

Reverse checks

• S009 · premise_and_result_audit — The class and its normalized representative are unique; u+kn gives other integer representatives.
• S008 · premise_and_result_audit — The quotient is an integer and the remainder really is 1.
• S007 · premise_and_result_audit — Recompute a·u with exact rational arithmetic, not rounded decimals.
• S006 · premise_and_result_audit — Normalize the inverse representative, not both Bezout coefficients.
• S005 · premise_and_result_audit — Multiply out the identity directly rather than trusting a gcd label.
• S004 · premise_and_result_audit — Check both the division identity and 0≤remainder<divisor.
• S003 · premise_and_result_audit — Check both the division identity and 0≤remainder<divisor.
• S002 · premise_and_result_audit — Check both the division identity and 0≤remainder<divisor.
• S001 · premise_and_result_audit — A modular inverse requires gcd(a,n)=1.

Result

(2, 37, 19, 1, Yes, unique_modulo_n)

The inverse representative is 19, unique modulo 37.

This question review and source binding

Review date: 2026-10-24

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