S001 · implies
Before
a=3, modulus=38
After
n=38≥2; seek u with 3u≡1 (mod 38)
Conditions: none
Fix the modulus and inverse condition; the integer product need not equal 1.
Step identifiers and dependencies
Rule: inverse_definition · Uses: G001
Explore related knowledge and questions →
Question 62: Normalize the Inverse Representative, Not the Bezout Coefficients
On this page
← Question derivation index · Original question batch
P250-0062 · q-20261014-advance-20261103-r07-modular-inverse-0062
Original question and givens
Use the original signed integer a=3 and modulus n=38≥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=38≥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.
Step-by-step derivation
S002 · implies
Before
divide 3 by 38
After
3=0·38+3
Conditions: 0≤3<38
The quotient is 0 and remainder 3; continue with the preceding divisor and remainder.
Step identifiers and dependencies
Rule: euclidean_division · Uses: G001, S001
S003 · implies
Before
divide 38 by 3
After
38=12·3+2
Conditions: 0≤2<3
The quotient is 12 and remainder 2; continue with the preceding divisor and remainder.
Step identifiers and dependencies
Rule: euclidean_division · Uses: G001, S002
S004 · implies
Before
divide 3 by 2
After
3=1·2+1
Conditions: 0≤1<2
The quotient is 1 and remainder 1; continue with the preceding divisor and remainder.
Step identifiers and dependencies
Rule: euclidean_division · Uses: G001, S003
S005 · implies
Before
divide 2 by 1
After
2=2·1+0
Conditions: 0≤0<1
The quotient is 2 and remainder 0; continue with the preceding divisor and remainder.
Step identifiers and dependencies
Rule: euclidean_division · Uses: G001, S004
S006 · implies
Before
last nonzero Euclidean remainder
After
gcd(3,38)=1; 3·(13)+38·(-1)=1
Conditions: none
Track integer linear combinations along the division chain to obtain this explicit Bezout identity.
Step identifiers and dependencies
Rule: bezout_identity · Uses: G001, S005
S007 · implies
Before
3·(13)+38·(-1)=1
After
13 mod 38=13; 0≤13<38
Conditions: none
The coefficient of a represents the inverse class; reduce it to the required representative interval.
Step identifiers and dependencies
Rule: normalize_residue · Uses: G001, S006
S008 · calculation
Before
a·u := mul(3, 13)
After
a·u = 39
Conditions: none
Multiply the original a by the normalized inverse.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S007
S009 · implies
Before
a·u=39
After
39=1·38+1 ⇒ a·u mod n=1
Conditions: none
The product minus 1 is an integer multiple of the modulus, verifying the inverse condition.
Step identifiers and dependencies
Rule: congruence_check · Uses: G001, S008
S010 · implies
Before
a·v≡a·u≡1 (mod n), gcd(a,n)=1
After
n divides v−u; if 0≤u,v<n then u=v
Conditions: none
From n|a(v−u), multiply the Bezout identity by v−u to get n|(v−u). Two normalized representatives differ by less than n in absolute value, so their difference is zero.
Step identifiers and dependencies
Rule: inverse_uniqueness · Uses: G001, S009
Reverse checks
S010· premise_and_result_audit — The class and its normalized representative are unique; u+kn gives other integer representatives.S009· premise_and_result_audit — The quotient is an integer and the remainder really is 1.S008· premise_and_result_audit — Recompute a·u with exact rational arithmetic, not rounded decimals.S007· premise_and_result_audit — Normalize the inverse representative, not both Bezout coefficients.S006· premise_and_result_audit — Multiply out the identity directly rather than trusting a gcd label.S005· premise_and_result_audit — Check both the division identity and 0≤remainder<divisor.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, 38, 13, 1, Yes, unique_modulo_n)
The inverse representative is 13, unique modulo 38.
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.
Source hashes and review receipts
input commit: 0f7be61e2c22317a4075561dc822c87d881a50dboriginal question SHA-256: abb4b298b1487e114aef3c3f18b40062582c64012f9dc8837c44382d12b6378ecandidate record SHA-256: 1d6c7a0be40ec47b97768ae554f1a15771d4ba8c139f82dfcfa00de6de525fa9semantic review receipt SHA-256: 4727d1bd957a9b7f6cadb7972ddb5ab80a31f5259dc5394c1dff2b71944ed36bquestion-first witness SHA-256: 51e18649133238ac992229f6e16542a5f3af53ca73b2262ab0524508ea937deeLean: NOT_RUN · human review: NOT_PERFORMED