Step-by-step derivation
S001 · implies
Before
source roles = [qf-ext18-gcd-coprime-classification, Nat_gcd, gcd-coprime-classification, no-form-field]
After
derived = [[a, b, gcd, gcd_equals1]]
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(0, 25)
After
GCD Euclid row0 ORIGINAL quotient times y = 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, S001
S003 · calculation
Before
GCD Euclid row0 ORIGINAL x minus qy := sub(12, 0)
After
GCD Euclid row0 ORIGINAL x minus qy = 12
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 = [12, 25, 0]
After
derived = [0, 12, [12, 25, 12]]
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(2, 12)
After
GCD Euclid row1 ORIGINAL quotient times y = 24
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(25, 24)
After
GCD Euclid row1 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, S005
S007 · implies
Before
source roles = [25, 12, 2]
After
derived = [24, 1, [25, 12, 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, S006
S008 · calculation
Before
GCD Euclid row2 ORIGINAL quotient times y := mul(12, 1)
After
GCD Euclid row2 ORIGINAL quotient times y = 12
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(12, 12)
After
GCD Euclid row2 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, S008
S010 · implies
Before
source roles = [12, 1, 12]
After
derived = [12, 0, [12, 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, S009
S011 · implies
Before
source roles = [12, 25, [[12, 25, 12], [25, 12, 1], [12, 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, S010
S012 · implies
Before
source roles = [12, 25, 1]
After
derived = [Yes]
Conditions: none
Coprime means ONLY gcd=1,not that both inputs are prime.(0,1)is coprime;(0,0)is not.
Step identifiers and dependencies
Rule: GCD_COPRIME_IFF_gcd1_NOT_both_prime · Uses: G001, S011