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

Original question and givens

Use the original signed integer a=3 and modulus n=28≥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=3 and modulus n=28≥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=3, modulus=28

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

divide 3 by 28

3=0·28+3

divide 28 by 3

28=9·3+1

divide 3 by 1

3=3·1+0

last nonzero Euclidean remainder

gcd(3,28)=1; 3·(-9)+28·(1)=1

3·(-9)+28·(1)=1

-9 mod 28=19; 0≤19<28

a·u := mul(3, 19)

a·u = 57

a·u=57

57=2·28+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

(3, 28, 19, 1, Yes, unique_modulo_n)

The inverse representative is 19, unique modulo 28.

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.