Back to the on-screen lesson ·
One linear equation in two unknowns over the integers: when it has a solution, what all of them look like, and which of them are non-negative.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to decide whether $ax + by = c$ has an integer solution by testing whether the greatest common divisor of the coefficients divides the right-hand side, produce a particular solution by scaling a Bézout identity, write the general solution with the correct steps, see the solutions as the lattice points on a line, and impose non-negativity as inequalities in the parameter.
Lesson 3 established that the integer combinations $ax + by$ are exactly the multiples of $\gcd(a, b)$, and that the extended Euclidean algorithm produces coefficients reaching the gcd itself.
That is the whole theory of this lesson, stated before the lesson begins. $ax + by = c$ is solvable exactly when $c$ is one of those multiples; a solution is got by scaling the Bézout identity; and the only thing left to work out is what the other solutions look like.
A Diophantine equation is one whose solutions are required to be integers. The requirement is the whole difficulty: $3x + 6y = 4$ has plenty of rational solutions and no integer ones.
A particular solution is one solution $(x_0, y_0)$. The general solution is the family containing all of them, written in terms of a parameter $t$ running over the integers.
Linear here means degree one in each unknown. Non-linear Diophantine equations are a different world: $x^{2} + y^{2} = z^{2}$ has infinitely many solutions and $x^{n} + y^{n} = z^{n}$ for $n > 2$ has none, and no method covers both.
Solvability. $ax + by = c$ has an integer solution if and only if $d = \gcd(a, b)$ divides $c$.
One direction: $d$ divides both terms on the left, so it divides $c$. The other: Bézout gives $ax_1 + by_1 = d$, and multiplying by $c/d$ — an integer, by hypothesis — gives a solution.
The general solution. If $(x_0, y_0)$ is one solution then every solution is $$x = x_0 + \frac{b}{d}t, \qquad y = y_0 - \frac{a}{d}t, \qquad t \in \mathbb{Z}.$$
These are solutions because the two changes cancel: $a \cdot \frac{b}{d} = b \cdot \frac{a}{d}$. And they are all of them: subtracting two solutions gives $a(x - x_0) = -b(y - y_0)$; dividing by $d$ gives $\frac{a}{d}(x - x_0) = -\frac{b}{d}(y - y_0)$ with $\frac{a}{d}$ and $\frac{b}{d}$ coprime, so $\frac{b}{d}$ divides $x - x_0$ — which is exactly the claim.
The steps are $b/d$ and $a/d$, not $b$ and $a$. Using the unreduced coefficients produces solutions, and misses $d - 1$ out of every $d$ of them.
The geometry. The equation is a line in the plane; the solutions are the lattice points on it. There are none at all when $d \nmid c$, and when there are any they are infinitely many, evenly spaced along the line with horizontal gap $b/d$. A line either misses the lattice entirely or meets it in an arithmetic progression — there is no middle case.
The same equation as a congruence. $ax + by = c$ has a solution exactly when $ax \equiv c \pmod{b}$ does, and the counts match: lesson 8's $d$ solutions modulo $b$ are the $d$ residue classes the parameter sweeps out. The two lessons are the same theorem written in two notations.
Another way: steps
Another way: example
$6x + 15y = 21$. $d = \gcd(6, 15) = 3$ and $3 \mid 21$, so solutions exist. Bézout: $6(-2) + 15(1) = 3$; scale by $21/3 = 7$ to get $6(-14) + 15(7) = 21$. General solution: $x = -14 + 5t$, $y = 7 - 2t$. For $x, y \ge 0$: $t \ge 2.8$ and $t \le 3.5$, so $t = 3$ only, giving $(1, 1)$.
Every applied version of this equation carries a condition the equation itself does not: nothing can be bought a negative number of times. That turns a solved problem into an unsolved one, and the extra step is short but is genuinely extra.
The method: find the general solution, then impose $x \ge 0$ and $y \ge 0$ as two inequalities in the parameter $t$. Each gives a bound, and the integers between the bounds are the admissible solutions. There may be many, exactly one, or none.
Take $7x + 11y = 100$. Since $\gcd(7, 11) = 1$, solutions exist: $7(-3) + 11(2) = 1$, so scaling by $100$ gives $x = -300$, $y = 200$, and the general solution is $x = -300 + 11t$, $y = 200 - 7t$. Non-negativity gives $t \ge 300/11 = 27.27\ldots$ and $t \le 200/7 = 28.57\ldots$, so $t = 28$, giving the single solution $(8, 4)$.
The number of non-negative solutions is roughly $c/(ab)$, so for a large right-hand side there are many and for a small one there are usually none. Which small values are unreachable is the Frobenius coin problem: for coprime $a$ and $b$, the largest $c$ with no non-negative solution is $ab - a - b$, and exactly half the values below that are unreachable. For $a = 7$ and $b = 11$ the largest unreachable amount is $59$.
That is a good place to see how much the integrality requirement costs. Over the rationals the equation is trivial and the answer is a line. Over the integers there is a solvability condition, an infinite family, and — once positivity is imposed — a counting problem with a genuinely intricate answer.
Assuming a solution exists. Test $\gcd(a, b) \mid c$ first. Searching cannot prove there is none, and for $6x + 9y = 20$ there is none to find.
Reporting one solution as the answer. There are infinitely many. The answer is the general solution, and a particular one is a representative.
Stepping by $b$ and $a$ instead of $b/d$ and $a/d$. Both give solutions; the unreduced steps miss most of them. For $6x + 15y = 21$ the step is $5$, not $15$.
Getting the signs the same way round. One unknown increases while the other decreases. Adding to both breaks the equation immediately, and substituting is the check.
Forgetting that positive is an extra condition. Integer does not mean non-negative. A word problem needs the inequalities imposed explicitly, and they may exclude everything.
$14x + 21y = 100$. Compute $d = \gcd(14, 21) = 7$.
The gcd before anything else.
$7 \nmid 100$, since $100 = 14 \cdot 7 + 2$. So there are no integer solutions at all.
One divisibility test replaces an unbounded search.
The reason: the left side is always a multiple of $7$, and $100$ is not. Over the rationals the equation is perfectly solvable — $x = 100/14$, $y = 0$ — so integrality is doing all the work.
The structural reason and the test are the same fact.
Crates hold $9$ or $14$ items and $100$ items are to be packed exactly. Solve $9x + 14y = 100$: $\gcd(9, 14) = 1$, so solutions exist.
Solvability first.
$9(-3) + 14(2) = 1$, so scaling by $100$ gives $x = -300$, $y = 200$, and the general solution is $x = -300 + 14t$, $y = 200 - 9t$.
The particular solution is wildly out of range, which is normal.
Impose $x \ge 0$ and $y \ge 0$: $t \ge 300/14 = 21.4\ldots$ and $t \le 200/9 = 22.2\ldots$, so $t = 22$, giving $x = 8$ and $y = 2$. Eight small crates and two large.
The inequalities cut infinitely many solutions down to one.
$d = \gcd(4, 6) = 2$ and $2 \mid 10$, so solutions exist.
The condition, checked before any work.
$4(-1) + 6(1) = 2$; scaling by $10/2 = 5$ gives $4(-5) + 6(5) = 10$, so $(x_0, y_0) = (-5, 5)$.
Scale the Bézout identity, do not guess.
The steps are $6/2 = 3$ and $4/2 = 2$, so the general solution is $x = -5 + 3t$, $y = 5 - 2t$. Checking $t = 2$: $(1, 1)$, and $4 + 6 = 10$.
The equation $3x + 5y = 1$ has the solution $x = 2$, $y = -1$ at $t = 0$, and the general solution steps $x$ by $5$ and $y$ by $-3$ each time $t$ increases. Fill in the table.
| Value of $x$ | Value of $y$ | |
|---|---|---|
| $t = 0$ | ||
| $t = 1$ | ||
| $t = 2$ |
A solution of $3x + 11y = 1$ has $y = -1$. What is $x$?
Answer:
Does $6x + 9y = 21$ have a solution in integers?
Mark the value of $x$ in the solution of $3x + 7y = 1$ that has $y = 1$. The line runs from $-15$ to $15$.
-15 |——————————| 15
Mark the position with a cross, then write the value:
Give the solution of $7x + 8y = 2$ that the extended Euclidean algorithm produces when its identity is scaled — the one with $y = 2$.
x is a, y is c
The solutions of a linear Diophantine equation have $x = 20 + 4t$ as $t$ runs over the integers. For which real $t$ is $x$ at least $0$? Give the set.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The equation $4x + 13y = 1$ has the solution $x = -3$, $y = 1$ at $t = 0$, and the general solution steps $x$ by $13$ and $y$ by $-4$ each time $t$ increases. Fill in the table.
| Value of $x$ | Value of $y$ | |
|---|---|---|
| $t = 0$ | ||
| $t = 1$ | ||
| $t = 2$ |
You can decide, solve and parametrise any linear Diophantine equation in two unknowns. Say in your own words why the steps in the general solution are the coefficients divided by the gcd rather than the coefficients themselves. Next: an equation of degree two, and the parametrisation it turns out to have.
9. Your turn: find all integer solutions of $4x + 6y = 10$, step 3