Linear Diophantine equations

It shows the greatest common divisor is not just the "biggest shared factor" but is actually reachable as an integer combination of $a$ and $b$ — the key fact that makes the solvability criterion for $ax+by=c$ work.

Consider the set $S=\{au+bv : u,v\in\mathbb{Z}\}\cap\mathbb{Z}_{>0}$ of all strictly positive integer combinations of $a$ and $b$. Since $a,b$ are not both $0$, $S$ is nonempty (it contains $|a|$ or $|b|$), so by the well-ordering principle $S$ has a least element $d=au_0+bv_0>0$.

We show $d\mid a$: divide $a=qd+r$ with $0\le r<d$. Then $r=a-qd=a-q(au_0+bv_0)=a(1-qu_0)+b(-qv_0)$ is itself an integer combination of $a,b$. If $r>0$ then $r$ would belong to $S$ and be smaller than $d$, contradicting minimality; so $r=0$, i.e. $d\mid a$. The identical argument with $b$ in place of $a$ shows $d\mid b$.

Since $d$ is a common divisor of $a$ and $b$, $d\le \gcd(a,b)$. Conversely, any common divisor $e$ of $a$ and $b$ divides $au_0+bv_0=d$, so $e\le d$; taking $e=\gcd(a,b)$ gives $\gcd(a,b)\le d$.

Combining both inequalities, $d=\gcd(a,b)$, and by construction $d=au_0+bv_0$, which is exactly Bézout's identity with $u=u_0,v=v_0$.

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

($\Rightarrow$) If $(x,y)$ is an integer solution, then $d=\gcd(a,b)$ divides both $ax$ and $by$, hence divides $ax+by=c$. So $d \mid c$ is necessary.

($\Leftarrow$) Suppose $d \mid c$, say $c=de$. By Bézout's identity there exist $u_0,v_0$ with $au_0+bv_0=d$. Multiplying by $e$ gives $a(u_0e)+b(v_0e)=de=c$, so $(x_0,y_0)=(u_0e,\,v_0e)$ is an integer solution. This proves solvability.

Now fix any solution $(x_0,y_0)$ and let $(x,y)$ be any other solution. Subtracting $ax_0+by_0=c$ from $ax+by=c$ gives $a(x-x_0)+b(y-y_0)=0$, i.e. $a(x-x_0)=-b(y-y_0)$. Dividing through by $d$: $\frac{a}{d}(x-x_0)=-\frac{b}{d}(y-y_0)$, and since $\gcd(a/d,\,b/d)=1$, the factor $\frac{b}{d}$ must divide $x-x_0$ (a standard consequence of coprimality: if $p\mid mn$ and $\gcd(p,m)=1$ then $p\mid n$). So $x-x_0=\frac{b}{d}t$ for some integer $t$, and substituting back gives $y-y_0=-\frac{a}{d}t$.

Conversely, for any integer $t$, substituting $x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t$ into $ax+by$ gives $ax_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=x_0+\dfrac{b}{d}t,\ \ y=y_0-\dfrac{a}{d}t\ \ (t\in\mathbb{Z})$.