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

Original question and givens

Use exact original integers a=120, b=180, c=1140 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=120, b=180, c=1140 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=120,b=180

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

Dioph Euclid step0 exact ratio := div(120, 180)

Dioph Euclid step0 exact ratio = 2/3

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

Dioph Euclid step0 divisor multiple = 0

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

Dioph Euclid step0 remainder = 120

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=180;old pair=[120, 180];exact ratio=2/3;floor quotient=0;old coefficient pairs=[[1, 0], [0, 1]]

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

Dioph Euclid step1 exact ratio := div(180, 120)

Dioph Euclid step1 exact ratio = 3/2

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

Dioph Euclid step1 divisor multiple = 120

Dioph Euclid step1 remainder := sub(180, 120)

Dioph Euclid step1 remainder = 60

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=120;old pair=[180, 120];exact ratio=3/2;floor quotient=1;old coefficient pairs=[[0, 1], [1, 0]]

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

Dioph Euclid step2 exact ratio := div(120, 60)

Dioph Euclid step2 exact ratio = 2

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

Dioph Euclid step2 divisor multiple = 120

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

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=60;old pair=[120, 60];exact ratio=2;floor quotient=2;old coefficient pairs=[[1, 0], [-1, 1]]

next remainder=0 in[0,60);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(120, -1)

Dioph ORIGINAL a times Bezout x = -120

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

Dioph ORIGINAL b times Bezout y = 180

Dioph original signed Bezout identity := sum(-120, 180)

Dioph original signed Bezout identity = 60

complete exact chain=[[120, 180, 0, 120], [180, 120, 1, 60], [120, 60, 2, 0]];terminal pair=[60, 0];sign-restored x=-1,y=1

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

Dioph target divided by positive gcd := div(1140, 60)

Dioph target divided by positive gcd = 19

ACTUAL original equation120*x+180*y=1140;positive gcd=60;exact c/d=19;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, 19)

Dioph particular x0 from scaled source Bezout = -19

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

Dioph particular y0 from scaled source Bezout = 19

Dioph original a times particular x0 := mul(120, -19)

Dioph original a times particular x0 = -2280

Dioph original b times particular y0 := mul(180, 19)

Dioph original b times particular y0 = 3420

Dioph particular original equation check := sum(-2280, 3420)

Dioph particular original equation check = 1140

Dioph normalized original a over gcd := div(120, 60)

Dioph normalized original a over gcd = 2

Dioph normalized original b over gcd := div(180, 60)

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(120, 3)

Dioph homogeneous a times x step = 360

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

Dioph homogeneous b times y step = -360

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

Dioph full homogeneous step cancellation = 0

particular original pair=[-19, 19] solves c=1140;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 gives-1*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

(-19, 19, 3, -2, x=-19+(3)t, y=19+(-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.