Diophantine Equations is the habit of solving equations under integer restrictions using divisibility, bounds, and modular constraints. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.
$$ax + by = c \text{ has integer solutions} \iff \gcd(a,b) \mid c$$
A linear equation in integers is solvable exactly when the gcd of the coefficients divides the target, and then all solutions form a single arithmetic family.
Why It Works
1
Let $g = \gcd(a,b)$. Every value of $ax + by$ is a multiple of $g$, so $g \mid c$ is necessary.
2
If $g \mid c$, Bézout gives $ax_0 + by_0 = g$; scaling by $c/g$ yields one solution $(x_1, y_1)$ to $ax + by = c$.
3
Given any solution, $a(x - x_1) + b(y - y_1) = 0$, so $\frac{a}{g}(x - x_1) = -\frac{b}{g}(y - y_1)$.
4
Since $\frac{a}{g}$ and $\frac{b}{g}$ are coprime, all solutions are $x = x_1 + \frac{b}{g} t$, $y = y_1 - \frac{a}{g} t$ for $t \in \mathbb{Z}$.
Worked Examples
Example 1
A vendor sells pens at $3$ coins and notebooks at $5$ coins. In how many ways can a customer spend exactly $31$ coins buying at least one of each?
1
Let $x$ pens and $y$ notebooks: $3x + 5y = 31$ with $x \ge 1$, $y \ge 1$.
2
Since $\gcd(3,5) = 1$ divides $31$, solutions exist. Solve mod $3$: $5y \equiv 31 \equiv 1 \pmod 3$, i.e. $2y \equiv 1$, so $y \equiv 2 \pmod 3$.
Add $144$ to both sides to factor (Simon's Favorite Factoring Trick): $xy - 12x - 12y + 144 = 144$, i.e. $(x - 12)(y - 12) = 144$.
3
Since $x, y > 0$ and $\frac1x < \frac1{12}$ forces $x > 12$, both $x - 12$ and $y - 12$ are positive divisors of $144 = 2^4 \cdot 3^2$.
4
The number of positive divisors of $144$ is $(4+1)(2+1) = 15$, and each divisor $d$ of $144$ gives $(x, y) = (12 + d,\ 12 + 144/d)$. So there are $15$ ordered pairs.
Answer:
$15$ ordered pairs, one for each positive divisor $d$ of $144$: $(x,y) = (12 + d,\ 12 + \tfrac{144}{d})$.
Going Deeper
Generalization: $ax + by = c$ is solvable in integers iff $\gcd(a,b) \mid c$, and the full solution set is the one-parameter family $x = x_0 + \frac{b}{g}t$, $y = y_0 - \frac{a}{g}t$. Nonlinear equations like $\frac1x+\frac1y=\frac1n$ or $xy + ax + by = c$ yield to Simon's Favorite Factoring Trick: complete the rectangle into a product equal to a constant, then enumerate divisors.
Where it appears: coin/postage counting, 'find all positive integers with...' problems, optimization over a Diophantine family (minimize/maximize subject to the constraint), and unit-fraction (Egyptian fraction) equations.
Pitfall: 'integer solutions exist' is not 'positive solutions exist' — the linear family is infinite over $\mathbb{Z}$ but only a finite window of $t$ keeps both variables in the required range. Always translate the sign/positivity constraints into bounds on the parameter $t$ before counting, and double-check whether the problem wants ordered or unordered pairs.
Spot the Signal
Look for problems where the key step is solving equations under integer restrictions using divisibility, bounds, and modular constraints.
You can describe the hard part as solving equations under integer restrictions using divisibility, bounds, and modular constraints, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.
Learn the Move
Start by identify the integer constraint that calls for diophantine equations, then rewrite the givens around it.
Name the relation that makes Diophantine Equations legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.
Avoid These Traps
Do not use Diophantine Equations just because the surface looks familiar; verify the required condition first.
Applying Diophantine Equations because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.
MathGrit Coach Note
Let diophantine equations reveal the integer structure; then compute only what remains.
Try it on:
Practice a contest problem where the key step is solving equations under integer restrictions using divisibility, bounds, and modular constraints.