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

Original question and givens

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

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

divide 2 by 35

2=0·35+2

divide 35 by 2

35=17·2+1

divide 2 by 1

2=2·1+0

last nonzero Euclidean remainder

gcd(2,35)=1; 2·(-17)+35·(1)=1

2·(-17)+35·(1)=1

-17 mod 35=18; 0≤18<35

a·u := mul(2, 18)

a·u = 36

a·u=36

36=1·35+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, 35, 18, 1, Yes, unique_modulo_n)

The inverse representative is 18, unique modulo 35.

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.