S001 · implies
Before
a=7, modulus=30
After
n=30≥2; seek u with 7u≡1 (mod 30)
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 54: Normalize the Inverse Representative, Not the Bezout Coefficients
On this page
← Question derivation index · Original question batch
P250-0054 · q-20261014-advance-20261103-r07-modular-inverse-0054
Original question and givens
Use the original signed integer a=7 and modulus n=30≥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=7 and modulus n=30≥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 7 by 30
After
7=0·30+7
Conditions: 0≤7<30
The quotient is 0 and remainder 7; continue with the preceding divisor and remainder.
Step identifiers and dependencies
Rule: euclidean_division · Uses: G001, S001
S003 · implies
Before
divide 30 by 7
After
30=4·7+2
Conditions: 0≤2<7
The quotient is 4 and remainder 2; continue with the preceding divisor and remainder.
Step identifiers and dependencies
Rule: euclidean_division · Uses: G001, S002
S004 · implies
Before
divide 7 by 2
After
7=3·2+1
Conditions: 0≤1<2
The quotient is 3 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(7,30)=1; 7·(13)+30·(-3)=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
7·(13)+30·(-3)=1
After
13 mod 30=13; 0≤13<30
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(7, 13)
After
a·u = 91
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=91
After
91=3·30+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
(7, 30, 13, 1, Yes, unique_modulo_n)
The inverse representative is 13, unique modulo 30.
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: bc016b630d9f6444aa1cbaaa2bb9ad266c9dbc0cc38cb5127219ada080150405candidate record SHA-256: 021c510da768f543f27511c95495978ce9d90ae6c957f34011756c4e1e90811fsemantic review receipt SHA-256: 4727d1bd957a9b7f6cadb7972ddb5ab80a31f5259dc5394c1dff2b71944ed36bquestion-first witness SHA-256: 51e18649133238ac992229f6e16542a5f3af53ca73b2262ab0524508ea937deeLean: NOT_RUN · human review: NOT_PERFORMED