Question 19691: Gcd Divisibility Is the Nondegenerate Integer-Solvability Criterion

Original question and givens

Use exact original integers a=-102, b=153, c=103 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 (a, b, c, gcd, both_coefficients_zero, solvable, boundary).

• G001 — Use exact original integers a=-102, b=153, c=103 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 (a, b, c, gcd, both_coefficients_zero, solvable, boundary).

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-solvability;original snapshot and mathematics retained

explicit ordered source output fields=[a, b, c, gcd, both_coefficients_zero, solvable, boundary]

ORIGINAL signed coefficients a=-102,b=153

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

Dioph Euclid step0 exact ratio := div(102, 153)

Dioph Euclid step0 exact ratio = 2/3

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

Dioph Euclid step0 divisor multiple = 0

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

Dioph Euclid step0 remainder = 102

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

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

Dioph Euclid step1 exact ratio := div(153, 102)

Dioph Euclid step1 exact ratio = 3/2

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

Dioph Euclid step1 divisor multiple = 102

Dioph Euclid step1 remainder := sub(153, 102)

Dioph Euclid step1 remainder = 51

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

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

Dioph Euclid step2 exact ratio := div(102, 51)

Dioph Euclid step2 exact ratio = 2

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

Dioph Euclid step2 divisor multiple = 102

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

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

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

Dioph ORIGINAL a times Bezout x = -102

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

Dioph ORIGINAL b times Bezout y = 153

Dioph original signed Bezout identity := sum(-102, 153)

Dioph original signed Bezout identity = 51

complete exact chain=[[102, 153, 0, 102], [153, 102, 1, 51], [102, 51, 2, 0]];terminal pair=[51, 0];sign-restored x=1,y=1

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

Dioph target divided by positive gcd := div(103, 51)

Dioph target divided by positive gcd = 103/51

ACTUAL original equation-102*x+153*y=103;positive gcd=51;exact c/d=103/51;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=No

Reverse checks

• 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

(-102, 153, 103, 51, No, No, gcd_divides_c_iff_integer_solution)

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.