Step-by-step derivation
S001 · implies
Before
source roles = [qf-ext18-gcd-euclid-trace, Nat_gcd, gcd-euclid-trace, no-form-field]
After
derived = [[a, b, ordered_Euclid_rows, gcd]]
Conditions: none
Check THIS bank interface:BASE equations use form/domain;BASE events/complement have no operation;factorials have no domain.ext18 uses local hyphens,other legacy operations underscores.Do not force every answer into a tuple or fraction.
Step identifiers and dependencies
Rule: R62_EXACT_source_keys_domain_operation_form_AND_output_types · Uses: G001
S002 · calculation
Before
GCD Euclid row0 ORIGINAL quotient times y := mul(1, 107)
After
GCD Euclid row0 ORIGINAL quotient times y = 107
Conditions: none
Use ORIGINAL operands and declared order for exact integer/rational arithmetic,not floats.Bounds are family-specific:do not revalidate derived values as RAW inputs or add blanket SAFE/n64 caps to BASE families.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S001
S003 · calculation
Before
GCD Euclid row0 ORIGINAL x minus qy := sub(168, 107)
After
GCD Euclid row0 ORIGINAL x minus qy = 61
Conditions: none
Use ORIGINAL operands and declared order for exact integer/rational arithmetic,not floats.Bounds are family-specific:do not revalidate derived values as RAW inputs or add blanket SAFE/n64 caps to BASE families.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S002
S004 · implies
Before
source roles = [168, 107, 1]
After
derived = [107, 61, [168, 107, 61]]
Conditions: none
With y≠0,divide to get x=qy+r and0≤r<y.A divisor common to x,y divides y,r,and the converse follows from x=qy+r,so common divisors are unchanged.Positive remainders strictly decrease,ensuring termination.
Step identifiers and dependencies
Rule: GCD_EUCLID_nonzero_divisor_exact_quotient_remainder_INVARIANT · Uses: G001, S003
S005 · calculation
Before
GCD Euclid row1 ORIGINAL quotient times y := mul(1, 61)
After
GCD Euclid row1 ORIGINAL quotient times y = 61
Conditions: none
Use ORIGINAL operands and declared order for exact integer/rational arithmetic,not floats.Bounds are family-specific:do not revalidate derived values as RAW inputs or add blanket SAFE/n64 caps to BASE families.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S004
S006 · calculation
Before
GCD Euclid row1 ORIGINAL x minus qy := sub(107, 61)
After
GCD Euclid row1 ORIGINAL x minus qy = 46
Conditions: none
Use ORIGINAL operands and declared order for exact integer/rational arithmetic,not floats.Bounds are family-specific:do not revalidate derived values as RAW inputs or add blanket SAFE/n64 caps to BASE families.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S005
S007 · implies
Before
source roles = [107, 61, 1]
After
derived = [61, 46, [107, 61, 46]]
Conditions: none
With y≠0,divide to get x=qy+r and0≤r<y.A divisor common to x,y divides y,r,and the converse follows from x=qy+r,so common divisors are unchanged.Positive remainders strictly decrease,ensuring termination.
Step identifiers and dependencies
Rule: GCD_EUCLID_nonzero_divisor_exact_quotient_remainder_INVARIANT · Uses: G001, S006
S008 · calculation
Before
GCD Euclid row2 ORIGINAL quotient times y := mul(1, 46)
After
GCD Euclid row2 ORIGINAL quotient times y = 46
Conditions: none
Use ORIGINAL operands and declared order for exact integer/rational arithmetic,not floats.Bounds are family-specific:do not revalidate derived values as RAW inputs or add blanket SAFE/n64 caps to BASE families.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S007
S009 · calculation
Before
GCD Euclid row2 ORIGINAL x minus qy := sub(61, 46)
After
GCD Euclid row2 ORIGINAL x minus qy = 15
Conditions: none
Use ORIGINAL operands and declared order for exact integer/rational arithmetic,not floats.Bounds are family-specific:do not revalidate derived values as RAW inputs or add blanket SAFE/n64 caps to BASE families.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S008
S010 · implies
Before
source roles = [61, 46, 1]
After
derived = [46, 15, [61, 46, 15]]
Conditions: none
With y≠0,divide to get x=qy+r and0≤r<y.A divisor common to x,y divides y,r,and the converse follows from x=qy+r,so common divisors are unchanged.Positive remainders strictly decrease,ensuring termination.
Step identifiers and dependencies
Rule: GCD_EUCLID_nonzero_divisor_exact_quotient_remainder_INVARIANT · Uses: G001, S009
S011 · calculation
Before
GCD Euclid row3 ORIGINAL quotient times y := mul(3, 15)
After
GCD Euclid row3 ORIGINAL quotient times y = 45
Conditions: none
Use ORIGINAL operands and declared order for exact integer/rational arithmetic,not floats.Bounds are family-specific:do not revalidate derived values as RAW inputs or add blanket SAFE/n64 caps to BASE families.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S010
S012 · calculation
Before
GCD Euclid row3 ORIGINAL x minus qy := sub(46, 45)
After
GCD Euclid row3 ORIGINAL x minus qy = 1
Conditions: none
Use ORIGINAL operands and declared order for exact integer/rational arithmetic,not floats.Bounds are family-specific:do not revalidate derived values as RAW inputs or add blanket SAFE/n64 caps to BASE families.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S011
S013 · implies
Before
source roles = [46, 15, 3]
After
derived = [45, 1, [46, 15, 1]]
Conditions: none
With y≠0,divide to get x=qy+r and0≤r<y.A divisor common to x,y divides y,r,and the converse follows from x=qy+r,so common divisors are unchanged.Positive remainders strictly decrease,ensuring termination.
Step identifiers and dependencies
Rule: GCD_EUCLID_nonzero_divisor_exact_quotient_remainder_INVARIANT · Uses: G001, S012
S014 · calculation
Before
GCD Euclid row4 ORIGINAL quotient times y := mul(15, 1)
After
GCD Euclid row4 ORIGINAL quotient times y = 15
Conditions: none
Use ORIGINAL operands and declared order for exact integer/rational arithmetic,not floats.Bounds are family-specific:do not revalidate derived values as RAW inputs or add blanket SAFE/n64 caps to BASE families.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S013
S015 · calculation
Before
GCD Euclid row4 ORIGINAL x minus qy := sub(15, 15)
After
GCD Euclid row4 ORIGINAL x minus qy = 0
Conditions: none
Use ORIGINAL operands and declared order for exact integer/rational arithmetic,not floats.Bounds are family-specific:do not revalidate derived values as RAW inputs or add blanket SAFE/n64 caps to BASE families.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S014
S016 · implies
Before
source roles = [15, 1, 15]
After
derived = [15, 0, [15, 1, 0]]
Conditions: none
With y≠0,divide to get x=qy+r and0≤r<y.A divisor common to x,y divides y,r,and the converse follows from x=qy+r,so common divisors are unchanged.Positive remainders strictly decrease,ensuring termination.
Step identifiers and dependencies
Rule: GCD_EUCLID_nonzero_divisor_exact_quotient_remainder_INVARIANT · Uses: G001, S015
S017 · implies
Before
source roles = [168, 107, [[168, 107, 61], [107, 61, 46], [61, 46, 15], [46, 15, 1], [15, 1, 0]]]
After
derived = [1, 0]
Conditions: none
At second value0 retain the last x.For nonzero x,gcd(x,0)=x;the two-way common-divisor invariant transfers this to the original pair.At(0,0)use the EXPLICIT convention gcd=0,not a claim that0 is the largest positive divisor.
Step identifiers and dependencies
Rule: GCD_TERMINAL_last_x_ZEROsecond_and_explicit_gcd00_convention · Uses: G001, S016