Question 19635: All Solutions Need the Gcd-Normalized Integer Parameter

Original question and givens

Use exact original integers a=-66, b=99, c=330 in a*x+b*y=c. The gcd d is nonnegative, and signed Bezout coefficients follow the deterministic extended Euclidean chain on absolute inputs, restoring input signs. For (a,b)≠(0,0), solvability is exactly d dividing c; finite searches do not supply all integer solutions. Handle (a,b)=(0,0) separately without division by d=0. Give (x0, y0, step_x, step_y, x_formula, y_formula, certificate).

• G001 — Use exact original integers a=-66, b=99, c=330 in a*x+b*y=c. The gcd d is nonnegative, and signed Bezout coefficients follow the deterministic extended Euclidean chain on absolute inputs, restoring input signs. For (a,b)≠(0,0), solvability is exactly d dividing c; finite searches do not supply all integer solutions. Handle (a,b)=(0,0) separately without division by d=0. Give (x0, y0, step_x, step_y, x_formula, y_formula, certificate).

Definition and scope

Use the original question domain, assumptions and cited MKO definitions. This item has second-context mathematical and bilingual review, with the model, answer and every arithmetic step independently recomputed from the original parameters; the source question remains a candidate.

• mko-linear-diophantine-equation

Step-by-step derivation

source operation=dioph-general-solution;original snapshot and mathematics retained

explicit ordered source output fields=[x0, y0, step_x, step_y, x_formula, y_formula, certificate]

ORIGINAL signed coefficients a=-66,b=99

start exact Euclidean chain on absolute values=[66, 99];nonnegative gcd;source deterministic coefficient recurrence

Dioph Euclid step0 exact ratio := div(66, 99)

Dioph Euclid step0 exact ratio = 2/3

Dioph Euclid step0 divisor multiple := mul(0, 99)

Dioph Euclid step0 divisor multiple = 0

Dioph Euclid step0 remainder := sub(66, 0)

Dioph Euclid step0 remainder = 66

Dioph Euclid step0 first coefficient multiple := mul(0, 0)

Dioph Euclid step0 first coefficient multiple = 0

Dioph Euclid step0 first coefficient difference := sub(1, 0)

Dioph Euclid step0 first coefficient difference = 1

Dioph Euclid step0 second coefficient multiple := mul(0, 1)

Dioph Euclid step0 second coefficient multiple = 0

Dioph Euclid step0 second coefficient difference := sub(0, 0)

Dioph Euclid step0 second coefficient difference = 0

step=0;positive divisor=99;old pair=[66, 99];exact ratio=2/3;floor quotient=0;old coefficient pairs=[[1, 0], [0, 1]]

next remainder=66 in[0,99);next signed absolute-input coefficients=[1, 0];common divisor set unchanged

Dioph Euclid step1 exact ratio := div(99, 66)

Dioph Euclid step1 exact ratio = 3/2

Dioph Euclid step1 divisor multiple := mul(1, 66)

Dioph Euclid step1 divisor multiple = 66

Dioph Euclid step1 remainder := sub(99, 66)

Dioph Euclid step1 remainder = 33

Dioph Euclid step1 first coefficient multiple := mul(1, 1)

Dioph Euclid step1 first coefficient multiple = 1

Dioph Euclid step1 first coefficient difference := sub(0, 1)

Dioph Euclid step1 first coefficient difference = -1

Dioph Euclid step1 second coefficient multiple := mul(1, 0)

Dioph Euclid step1 second coefficient multiple = 0

Dioph Euclid step1 second coefficient difference := sub(1, 0)

Dioph Euclid step1 second coefficient difference = 1

step=1;positive divisor=66;old pair=[99, 66];exact ratio=3/2;floor quotient=1;old coefficient pairs=[[0, 1], [1, 0]]

next remainder=33 in[0,66);next signed absolute-input coefficients=[-1, 1];common divisor set unchanged

Dioph Euclid step2 exact ratio := div(66, 33)

Dioph Euclid step2 exact ratio = 2

Dioph Euclid step2 divisor multiple := mul(2, 33)

Dioph Euclid step2 divisor multiple = 66

Dioph Euclid step2 remainder := sub(66, 66)

Dioph Euclid step2 remainder = 0

Dioph Euclid step2 first coefficient multiple := mul(2, -1)

Dioph Euclid step2 first coefficient multiple = -2

Dioph Euclid step2 first coefficient difference := sub(1, -2)

Dioph Euclid step2 first coefficient difference = 3

Dioph Euclid step2 second coefficient multiple := mul(2, 1)

Dioph Euclid step2 second coefficient multiple = 2

Dioph Euclid step2 second coefficient difference := sub(0, 2)

Dioph Euclid step2 second coefficient difference = -2

step=2;positive divisor=33;old pair=[66, 33];exact ratio=2;floor quotient=2;old coefficient pairs=[[1, 0], [-1, 1]]

next remainder=0 in[0,33);next signed absolute-input coefficients=[3, -2];common divisor set unchanged

Dioph restore original a sign := mul(-1, -1)

Dioph restore original a sign = 1

Dioph restore original b sign := mul(1, 1)

Dioph restore original b sign = 1

Dioph ORIGINAL a times Bezout x := mul(-66, 1)

Dioph ORIGINAL a times Bezout x = -66

Dioph ORIGINAL b times Bezout y := mul(99, 1)

Dioph ORIGINAL b times Bezout y = 99

Dioph original signed Bezout identity := sum(-66, 99)

Dioph original signed Bezout identity = 33

complete exact chain=[[66, 99, 0, 66], [99, 66, 1, 33], [66, 33, 2, 0]];terminal pair=[33, 0];sign-restored x=1,y=1

a*x+b*y=33=nonnegative gcd d=33;gcd from invariance and terminal gcd(d,0)=d

Dioph target divided by positive gcd := div(330, 33)

Dioph target divided by positive gcd = 10

ACTUAL original equation-66*x+99*y=330;positive gcd=33;exact c/d=10;Bezout coefficients=[1, 1]

d divides both coefficients,so ANY integer solution requires d divides c;conversely integer c/d scales Bezout to a solution;solvable=Yes

Dioph particular x0 from scaled source Bezout := mul(1, 10)

Dioph particular x0 from scaled source Bezout = 10

Dioph particular y0 from scaled source Bezout := mul(1, 10)

Dioph particular y0 from scaled source Bezout = 10

Dioph original a times particular x0 := mul(-66, 10)

Dioph original a times particular x0 = -660

Dioph original b times particular y0 := mul(99, 10)

Dioph original b times particular y0 = 990

Dioph particular original equation check := sum(-660, 990)

Dioph particular original equation check = 330

Dioph normalized original a over gcd := div(-66, 33)

Dioph normalized original a over gcd = -2

Dioph normalized original b over gcd := div(99, 33)

Dioph normalized original b over gcd = 3

Dioph signed general y step := mul(-1, -2)

Dioph signed general y step = 2

Dioph homogeneous a times x step := mul(-66, 3)

Dioph homogeneous a times x step = -198

Dioph homogeneous b times y step := mul(99, 2)

Dioph homogeneous b times y step = 198

Dioph full homogeneous step cancellation := sum(-198, 198)

Dioph full homogeneous step cancellation = 0

particular original pair=[10, 10] solves c=330;normalized coprime A=-2,B=3;step pair=[3, 2]

for EVERY integer t,x=x0+(3)t,y=y0+(2)t gives left side=c+t*0=c;all displayed solutions valid

ANY other integer solution;differences dx=x-x0,dy=y-y0 satisfy A*dx+B*dy=0;A=-2,B=3;source Bezout gives1*A+1*B=1

dx=B*(-(1)*dy+(1)*dx),so t=dx/B is an INTEGER;B!=0 then dy=-A*t;ALL solutions have the displayed form

Reverse checks

• S047 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S046 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S045 · premise_and_result_audit — Recompute Dioph full homogeneous step cancellation with exact rational arithmetic, not rounded decimals.
• S044 · premise_and_result_audit — Recompute Dioph homogeneous b times y step with exact rational arithmetic, not rounded decimals.
• S043 · premise_and_result_audit — Recompute Dioph homogeneous a times x step with exact rational arithmetic, not rounded decimals.
• S042 · premise_and_result_audit — Recompute Dioph signed general y step with exact rational arithmetic, not rounded decimals.
• S041 · premise_and_result_audit — Recompute Dioph normalized original b over gcd with exact rational arithmetic, not rounded decimals.
• S040 · premise_and_result_audit — Recompute Dioph normalized original a over gcd with exact rational arithmetic, not rounded decimals.
• S039 · premise_and_result_audit — Recompute Dioph particular original equation check with exact rational arithmetic, not rounded decimals.
• S038 · premise_and_result_audit — Recompute Dioph original b times particular y0 with exact rational arithmetic, not rounded decimals.
• S037 · premise_and_result_audit — Recompute Dioph original a times particular x0 with exact rational arithmetic, not rounded decimals.
• S036 · premise_and_result_audit — Recompute Dioph particular y0 from scaled source Bezout with exact rational arithmetic, not rounded decimals.
• S035 · premise_and_result_audit — Recompute Dioph particular x0 from scaled source Bezout with exact rational arithmetic, not rounded decimals.
• S034 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S033 · premise_and_result_audit — Recompute Dioph target divided by positive gcd with exact rational arithmetic, not rounded decimals.
• S032 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S031 · premise_and_result_audit — Recompute Dioph original signed Bezout identity with exact rational arithmetic, not rounded decimals.
• S030 · premise_and_result_audit — Recompute Dioph ORIGINAL b times Bezout y with exact rational arithmetic, not rounded decimals.
• S029 · premise_and_result_audit — Recompute Dioph ORIGINAL a times Bezout x with exact rational arithmetic, not rounded decimals.
• S028 · premise_and_result_audit — Recompute Dioph restore original b sign with exact rational arithmetic, not rounded decimals.
• S027 · premise_and_result_audit — Recompute Dioph restore original a sign with exact rational arithmetic, not rounded decimals.
• S026 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S025 · premise_and_result_audit — Recompute Dioph Euclid step2 second coefficient difference with exact rational arithmetic, not rounded decimals.
• S024 · premise_and_result_audit — Recompute Dioph Euclid step2 second coefficient multiple with exact rational arithmetic, not rounded decimals.
• S023 · premise_and_result_audit — Recompute Dioph Euclid step2 first coefficient difference with exact rational arithmetic, not rounded decimals.
• S022 · premise_and_result_audit — Recompute Dioph Euclid step2 first coefficient multiple with exact rational arithmetic, not rounded decimals.
• S021 · premise_and_result_audit — Recompute Dioph Euclid step2 remainder with exact rational arithmetic, not rounded decimals.
• S020 · premise_and_result_audit — Recompute Dioph Euclid step2 divisor multiple with exact rational arithmetic, not rounded decimals.
• S019 · premise_and_result_audit — Recompute Dioph Euclid step2 exact ratio with exact rational arithmetic, not rounded decimals.
• S018 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S017 · premise_and_result_audit — Recompute Dioph Euclid step1 second coefficient difference with exact rational arithmetic, not rounded decimals.
• S016 · premise_and_result_audit — Recompute Dioph Euclid step1 second coefficient multiple with exact rational arithmetic, not rounded decimals.
• S015 · premise_and_result_audit — Recompute Dioph Euclid step1 first coefficient difference with exact rational arithmetic, not rounded decimals.
• S014 · premise_and_result_audit — Recompute Dioph Euclid step1 first coefficient multiple with exact rational arithmetic, not rounded decimals.
• S013 · premise_and_result_audit — Recompute Dioph Euclid step1 remainder with exact rational arithmetic, not rounded decimals.
• S012 · premise_and_result_audit — Recompute Dioph Euclid step1 divisor multiple with exact rational arithmetic, not rounded decimals.
• S011 · premise_and_result_audit — Recompute Dioph Euclid step1 exact ratio with exact rational arithmetic, not rounded decimals.
• S010 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S009 · premise_and_result_audit — Recompute Dioph Euclid step0 second coefficient difference with exact rational arithmetic, not rounded decimals.
• S008 · premise_and_result_audit — Recompute Dioph Euclid step0 second coefficient multiple with exact rational arithmetic, not rounded decimals.
• S007 · premise_and_result_audit — Recompute Dioph Euclid step0 first coefficient difference with exact rational arithmetic, not rounded decimals.
• S006 · premise_and_result_audit — Recompute Dioph Euclid step0 first coefficient multiple with exact rational arithmetic, not rounded decimals.
• S005 · premise_and_result_audit — Recompute Dioph Euclid step0 remainder with exact rational arithmetic, not rounded decimals.
• S004 · premise_and_result_audit — Recompute Dioph Euclid step0 divisor multiple with exact rational arithmetic, not rounded decimals.
• S003 · premise_and_result_audit — Recompute Dioph Euclid step0 exact ratio with exact rational arithmetic, not rounded decimals.
• S002 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S001 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.

Result

(10, 10, 3, 2, x=10+(3)t, y=10+(2)t, all_and_only_integer_solutions_for_t_in_Z)

The full substitutions and premise checks give the original answer; source identity,format and status are unchanged.

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.