[proofplan] The equation $ax + by = c$ is solvable in integers exactly when $c$ lies in the set $I = \{\lambda a + \mu b : \lambda, \mu \in \mathbb{Z}\}$ of integer linear combinations of $a$ and $b$. By the principal-ideal structure of $I$, this set equals $d\mathbb{Z}$ where $d = \gcd(a, b)$. The "only if" direction follows because $d \mid a$ and $d \mid b$ force $d \mid (ax + by) = c$. The "if" direction uses Bezout's identity — which exhibits $d$ itself as an integer combination of $a$ and $b$ — and then scales the Bezout coefficients by $c/d$. [/proofplan] [step:Set notation and name the generator of the set of linear combinations] Let $a, b, c \in \mathbb{Z}$ with $a, b$ not both zero, and define \begin{align*} I &:= \{\lambda a + \mu b : \lambda, \mu \in \mathbb{Z}\}. \end{align*} The claim $ax + by = c$ has an integer solution is exactly the statement $c \in I$. By the [Every Integer Ideal is Principal](/theorems/1695) theorem applied to the two-element tuple $(a, b)$ (not both zero by hypothesis), there exists a unique positive integer $d \geq 1$ with $I = d\mathbb{Z}$. We identify this $d$ with $\gcd(a, b)$ in the next step. [/step] [step:Identify $d$ with $\gcd(a, b)$] [claim:The positive generator $d$ of $I$ equals $\gcd(a, b)$] [proof] We show $d$ satisfies the two defining properties of $\gcd(a, b)$: (i) $d \mid a$ and $d \mid b$, and (ii) any common divisor of $a$ and $b$ divides $d$. (i) Since $a = 1 \cdot a + 0 \cdot b \in I = d\mathbb{Z}$, we have $d \mid a$. Similarly $b = 0 \cdot a + 1 \cdot b \in I = d\mathbb{Z}$, so $d \mid b$. (ii) Let $e \in \mathbb{Z}$ with $e \mid a$ and $e \mid b$. Since $d \in I = d\mathbb{Z}$, there exist $r, s \in \mathbb{Z}$ with $d = ra + sb$. Then $e \mid ra$ and $e \mid sb$, so $e \mid (ra + sb) = d$. Properties (i) and (ii) together with the convention $\gcd(a, b) > 0$ characterise $\gcd(a, b)$ uniquely, so $d = \gcd(a, b)$. We write $(a, b) := \gcd(a, b)$ from here on. [/proof] [/claim] [/step] [step:Prove the only-if direction: if $ax + by = c$ has an integer solution, then $(a, b) \mid c$] Suppose $x, y \in \mathbb{Z}$ satisfy $ax + by = c$. Let $d = (a, b)$. By part (i) of the claim in the previous step, $d \mid a$ and $d \mid b$. Hence $d \mid ax$ and $d \mid by$, so \begin{align*} d &\mid (ax + by) = c, \end{align*} as required. [/step] [step:Prove the if direction via Bezout: if $(a, b) \mid c$, construct an explicit solution] Suppose $d = (a, b)$ divides $c$. We construct integers $x, y$ with $ax + by = c$. By [Bezout's Identity](/theorems/???) — which is equivalent to the statement $d \in I$, already established — there exist $r, s \in \mathbb{Z}$ with \begin{align*} r a + s b &= d. \end{align*} Since $d \mid c$, write $c = k d$ for some $k \in \mathbb{Z}$. Multiplying the Bezout relation by $k$, \begin{align*} (kr) a + (ks) b &= k d = c. \end{align*} Setting $x := kr$ and $y := ks$ yields the required integer solution. [guided] The strategy is to leverage the special element $d = (a, b)$, which by the principal-ideal description of $I$ is already known to be expressible as an integer combination $ra + sb$. These coefficients $r, s$ are the Bezout coefficients; they can be computed explicitly by running the extended Euclidean algorithm on $(a, b)$, although for the purpose of existence we only need to know they exist. Why does this work for general $c$, not just $c = d$? Because $c$ is assumed to be a multiple of $d$, say $c = kd$. Integer combinations of $a$ and $b$ are closed under multiplication by any integer: if $ra + sb = d$, then $(kr)a + (ks)b = k(ra + sb) = kd = c$. The Bezout coefficients for $d$ thus scale by $k$ to give Bezout coefficients for $c$. What would fail if $d \nmid c$? The "only if" direction of the theorem rules this out — in that case $c \notin I = d\mathbb{Z}$, so no integer combination of $a$ and $b$ can equal $c$, and no scaling of a Bezout relation $ra + sb = d$ could produce $c$ on the right-hand side (only multiples of $d$ can appear). [/guided] [/step] [step:Combine both directions to conclude] In Step 3 we showed: $ax + by = c$ solvable in $\mathbb{Z}$ implies $(a, b) \mid c$. In Step 4 we showed the converse: $(a, b) \mid c$ implies the existence of an integer solution. Therefore $ax + by = c$ has an integer solution if and only if $(a, b) \mid c$, as stated. [/step]