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

Original question and givens

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

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

divide 5 by 36

5=0·36+5

divide 36 by 5

36=7·5+1

divide 5 by 1

5=5·1+0

last nonzero Euclidean remainder

gcd(5,36)=1; 5·(-7)+36·(1)=1

5·(-7)+36·(1)=1

-7 mod 36=29; 0≤29<36

a·u := mul(5, 29)

a·u = 145

a·u=145

145=4·36+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

(5, 36, 29, 1, Yes, unique_modulo_n)

The inverse representative is 29, unique modulo 36.

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.