How to find the number of solutions to a linear Diophantine equation?

**Theorem:** The linear Diophantine equation $ax + by = c$ has integer solutions iff $\gcd(a, b) \mid c$. **General Solution Method:** 1. Compute $g = \gcd(a, b)$. If $g \ mid c$, no solutions. 2. Find one particular solution $(x_0, y_0)$ using the Extended Euclidean Algorithm. 3. All solutions are given by: $$x = x_0 + \frac{b}{g} \cdot t, \quad y = y_0 - \frac{a}{g} \cdot t, \quad t \in \mathbb{Z}$$ **Example: $3x + 5y = 17$** **Step 1:** $\gcd(3, 5) = 1$, and $1 \mid 17$, so solutions exist. **Step 2:** Find a particular solution. By inspection, $3(4) + 5(1) = 12 + 5 = 17$, so $(x_0, y_0) = (4, 1)$. **Step 3:** General solution: $$x = 4 + 5t, \quad y = 1 - 3t, \quad t \in \mathbb{Z}$$ **Non-negative solutions:** Require $x \geq 0$ and $y \geq 0$: $$4 + 5t \geq 0 \Rightarrow t \geq -0.8 \Rightarrow t \geq 0$$ $$1 - 3t \geq 0 \Rightarrow t \leq 1/3 \Rightarrow t \leq 0$$ So $t = 0$ only, giving $(x, y) = (4, 1)$ as the unique non-negative solution. **Systematic finding of particular solution via Extended Euclidean Algorithm:** $5 = 1 \cdot 3 + 2$, $3 = 1 \cdot 2 + 1$. Back-substitute: $1 = 3 - 1(2) = 3 - 1(5 - 1(3)) = 2(3) - 1(5)$. Multiply by 17: $17 = 34(3) - 17(5)$, so $3(34) + 5(-17) = 17$, giving $(x_0, y_0) = (34, -17)$, and the general solution $x = 34 + 5t, y = -17 - 3t$, which is equivalent to $(4, 1)$ with $t = -6$.