MathLabs
TheoremProved

Solvability and the general solution

Statement

ax+by=cax+by=c has an integer solution if and only if d∣cd \mid c where d=gcd⁡(a,b)d=\gcd(a,b); when it does, and (x0,y0)(x_0,y_0) is one solution, every integer solution is exactly x=x0+bdt,  y=y0−adt  (t∈Z)x=x_0+\dfrac{b}{d}t,\ \ y=y_0-\dfrac{a}{d}t\ \ (t\in\mathbb{Z}).

Why is it true?

It completely closes the problem: one divisibility check decides solvability, and once you have any single solution, a one-parameter family via tt hands you every other solution — no guessing required.

Proof sketch

(⇒\Rightarrow) If (x,y)(x,y) is an integer solution, then d=gcd⁡(a,b)d=\gcd(a,b) divides both axax and byby, hence divides ax+by=cax+by=c. So d∣cd \mid c is necessary.

(⇐\Leftarrow) Suppose d∣cd \mid c, say c=dec=de. By Bézout's identity there exist u0,v0u_0,v_0 with au0+bv0=dau_0+bv_0=d. Multiplying by ee gives a(u0e)+b(v0e)=de=ca(u_0e)+b(v_0e)=de=c, so (x0,y0)=(u0e, v0e)(x_0,y_0)=(u_0e,\,v_0e) is an integer solution. This proves solvability.

Now fix any solution (x0,y0)(x_0,y_0) and let (x,y)(x,y) be any other solution. Subtracting ax0+by0=cax_0+by_0=c from ax+by=cax+by=c gives a(x−x0)+b(y−y0)=0a(x-x_0)+b(y-y_0)=0, i.e. a(x−x0)=−b(y−y0)a(x-x_0)=-b(y-y_0). Dividing through by dd: ad(x−x0)=−bd(y−y0)\frac{a}{d}(x-x_0)=-\frac{b}{d}(y-y_0), and since gcd⁡(a/d, b/d)=1\gcd(a/d,\,b/d)=1, the factor bd\frac{b}{d} must divide x−x0x-x_0 (a standard consequence of coprimality: if p∣mnp\mid mn and gcd⁡(p,m)=1\gcd(p,m)=1 then p∣np\mid n). So x−x0=bdtx-x_0=\frac{b}{d}t for some integer tt, and substituting back gives y−y0=−adty-y_0=-\frac{a}{d}t.

Conversely, for any integer tt, substituting x=x0+bdt, y=y0−adtx=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t into ax+byax+by gives ax0+by0+t(abd−abd)=c+0=cax_0+by_0+t\left(\frac{ab}{d}-\frac{ab}{d}\right)=c+0=c, confirming every such pair is indeed a solution. Hence the solution set is exactly x=x0+bdt,  y=y0−adt  (t∈Z)x=x_0+\dfrac{b}{d}t,\ \ y=y_0-\dfrac{a}{d}t\ \ (t\in\mathbb{Z}).

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. Wikipedia contributors (2024). Bézout's identity
  2. G. H. Hardy, E. M. Wright (2008). An Introduction to the Theory of Numbers