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

Original question and givens

Use the original signed integer a=2 and modulus n=51≥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=51≥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=51

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

divide 2 by 51

2=0·51+2

divide 51 by 2

51=25·2+1

divide 2 by 1

2=2·1+0

last nonzero Euclidean remainder

gcd(2,51)=1; 2·(-25)+51·(1)=1

2·(-25)+51·(1)=1

-25 mod 51=26; 0≤26<51

a·u := mul(2, 26)

a·u = 52

a·u=52

52=1·51+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, 51, 26, 1, Yes, unique_modulo_n)

The inverse representative is 26, unique modulo 51.

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.