Question 328: A Modular Inverse Exists Exactly for a Unit

Original question and givens

Use the original signed integer a=2 and modulus n=29≥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. Give (a,n,gcd,exists?,inverse), with inverse=null for a nonunit.

• G001 — Use the original signed integer a=2 and modulus n=29≥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. Give (a,n,gcd,exists?,inverse), with inverse=null for a nonunit.

Definition and scope

Integer a and modulus n≥2. An inverse exists exactly when gcd(a,n)=1; normalize the representative into [0,n).

• mko-modular-inverse

Step-by-step derivation

a=2; n=29≥2

compute gcd and a Bezout certificate before inversion

divide 2 by 29

2=0·29+2

divide 29 by 2

29=14·2+1

divide 2 by 1

2=2·1+0

a·x := mul(2, -14)

a·x = -28

n·y := mul(29, 1)

n·y = 29

Bezout value := sum(-28, 29)

Bezout value = 1

2·(-14)+29·(1)=1

inverse representative=15; 2·15≡1 (mod 29)

Reverse checks

• S008 · premise_and_result_audit — Check integer identities, remainder bounds and gcd conditions; congruence is not integer equality.
• S007 · premise_and_result_audit — Recompute Bezout value with exact rational arithmetic, not rounded decimals.
• S006 · premise_and_result_audit — Recompute n·y with exact rational arithmetic, not rounded decimals.
• S005 · premise_and_result_audit — Recompute a·x with exact rational arithmetic, not rounded decimals.
• S004 · premise_and_result_audit — Check integer identities, remainder bounds and gcd conditions; congruence is not integer equality.
• S003 · premise_and_result_audit — Check integer identities, remainder bounds and gcd conditions; congruence is not integer equality.
• S002 · premise_and_result_audit — Check integer identities, remainder bounds and gcd conditions; congruence is not integer equality.
• S001 · premise_and_result_audit — Check integer identities, remainder bounds and gcd conditions; congruence is not integer equality.

Result

(2, 29, 1, Yes, 15)

The full substitutions and premise audits recover the original answer, retaining its field order and verdict meanings.

This question review and source binding

Review date: 2026-10-26

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