Diophantine equations

Let $x$ be the number of 3-object packs and $y$ the number of 5-object packs. The letter is a name for a number we have not chosen yet. If $x = 3$, the first kind contributes $3 + 3 + 3 = 3 \times 3 = 9$ objects. If $y = 4$, the second kind contributes $5 + 5 + 5 + 5 = 5 \times 4 = 20$ objects. Together they give $9 + 20 = 29$.

The symbol $\in$ means ‘belongs to’. The braces list the allowed numbers, and the dots mean that the list continues. Here $x$ and $y$ may be 0, because we may choose none of one kind. They cannot be negative, because we cannot take a negative number of packs. They also cannot be fractions. We call 0, 1, 2, … the nonnegative integers.

Use the two sliders below to change the numbers of packs. A green outline holds 3 dots, and an amber outline holds 5. Each dot is one object. Keep the target 29 fixed and watch how $3x$ and $5y$ contribute to the total. Then try $x = 8$ and $y = 1$: $3 \times 8 + 5 \times 1 = 24 + 5 = 29$ gives another choice.

Now let us separate the equation from this particular story. An integer can also be negative: …, $-3, -2, -1, 0, 1, 2, 3$, …. We write $\mathbb Z$ for the collection of all integers. For example, $x = -2$ and $y = 7$ satisfy $3 \times (-2) + 5 \times 7 = -6 + 35 = 29$. This is an integer solution of the equation, but it is not a valid choice of packs. We must state which of these questions we are answering.

An equation whose unknowns must be integers is called a Diophantine equation, after the Greek mathematician Diophantus, who studied such problems. Our linear examples will have no integer solutions or infinitely many; a later nonlinear example will have exactly six. The restriction on the unknowns is the essential point.

We do not need to guess both numbers at once. Once $x$ is chosen, the total 29 tells us what $y$ must be. Subtracting $3x$ from both sides leaves $5y$ on the left. Dividing both sides by the nonzero number 5 then gives $y$.

For $x = 0$, this gives $y = (29 - 3 \times 0)/5 = 29/5 = 5.8$. The equality is true: $3 \times 0 + 5 \times 5.8 = 29$. But 5.8 is not an integer. For $x = 3$, we get $y = (29 - 9)/5 = 20/5 = 4$, which is an integer. Solving the equation over the real numbers allows both answers; solving it over the integers allows only the second. Here real numbers include whole numbers and fractions, as well as other positions on the number line.

To make this distinction visible, we use two number lines that cross at zero. The horizontal one records $x$, and the vertical one records $y$. The pair (3, 4) means move 3 units to the right from the crossing, then 4 units up. A grey dot is placed wherever both coordinates are integers. These regularly spaced dots form an integer lattice. We are looking for calculated points that land exactly on these dots, not between them.

Why does the purple graph form a straight line? If $x$ changes by an amount $h$, substituting $x + h$ gives $y = (29 - 3x - 3h)/5 = (29 - 3x)/5 - 3h/5$. So a horizontal change of $h$ always produces a vertical change of $-3h/5$. For $h \ne 0$, dividing the vertical change $-3h/5$ by the horizontal change $h$ gives $-3/5$. The ratio is fixed. This is exactly a straight line with slope $-3/5$; the word slope records vertical change divided by horizontal change. The line includes fractional coordinates too. Only its integer-coordinate points answer the integer question.

For nonnegative pack counts, $x$ cannot exceed 9: if $x \ge 10$, the first kind alone contributes at least $3 \times 10 = 30$, already more than 29. Thus checking $x = 0$ through 9 really does check every nonnegative possibility in this particular problem. But it does not check every integer solution, because $x$ could be negative and $y$ could then be larger. We need a proof that reaches beyond this finite picture.

Change the pack sizes to 6 and 9, and ask for a total of 31. Before trying lots of pairs, notice that both pack sizes are multiples of 3. Any number of either kind still contributes a multiple of 3. Adding them cannot change this fact.

If $x$ and $y$ are integers, then $2x + 3y$ is an integer. The left side is therefore exactly 3 times an integer. The number 31 is not: dividing it by 3 gives 10 with remainder 1. This proves that $6x + 9y = 31$ has no integer solution, even if negative $x$ and $y$ are allowed. We did not fail to find a solution; we proved that one cannot exist.

Let us write the same reasoning for positive integer coefficients $a$ and $b$ and an integer target $c$. A positive integer $d$ divides $a$ if $a = dA$ for some integer $A$; we write $d \mid a$. A common divisor divides both $a$ and $b$. The largest positive common divisor is their greatest common divisor, written $\gcd(a, b)$. It exists here because 1 is a common divisor, while no positive divisor of $a$ can exceed the positive number $a$.

If $ax + by = c$ has an integer solution, the last line says $c = d$ times the integer $Ax + By$. Therefore $d \mid c$ is necessary. The word necessary means that a solution cannot exist without this condition. It does not yet mean that the condition guarantees a solution. That converse is our next task.

Our goal is to express the greatest common divisor as $a \times$ an integer plus $b \times$ an integer. If we can do that, multiplying both integers by $c/d$ will produce the target $c$ whenever $d$ divides $c$. Division with a remainder gives us a way to make this expression.

First see the whole calculation with 3 and 5

Take away one group of 3 from 5; the remainder is 2. Then take away one group of 2 from 3; the remainder is 1. Finally 2 contains two groups of 1 with nothing left. At each stage the next remainder is smaller than the number we divided by.

The last nonzero remainder is 1. To write it using the original 3 and 5, read the second equation backwards: $1 = 3 - 2$. The first equation says $2 = 5 - 3$. Replace the 2 by that expression, then distribute the minus sign.

So $(58, -29)$ is an integer solution of $3x + 5y = 29$. Check it directly: $3 \times 58 = 174, 5 \times (-29) = -145$, and $174 - 145 = 29$. It is not a pack choice, but we have achieved the current goal of finding one integer solution. Later we will move from one solution to all the others, including (3, 4).

Why does the division process always stop?

For two positive integers $U$ and $V$, keep taking away $V$ from $U$ until the amount left is less than $V$. If $U < V$, we take away zero groups. Because each subtraction reduces a nonnegative amount by at least 1, only finitely many subtractions are possible. Counting the groups gives a nonnegative integer $q$ and a remainder $r$ with $U = qV + r$ and $0 \le r < V$.

When $r$ is nonzero, repeat with the pair $(V, r)$. The second number keeps becoming a strictly smaller positive integer. It cannot decrease forever: starting from $V$, it can pass through at most the positive numbers $V - 1$ down to 1. Eventually a remainder is zero. This repeated division is called the Euclidean algorithm.

Why is the final nonzero entry the $\gcd$?

We must show that replacing $(U, V)$ by $(V, r)$ preserves every common divisor. If $k$ divides $U$ and $V$, write $U = km$ and $V = kn$. From $r = U - qV$ we get $r = km - qkn = k(m - qn)$, so $k$ divides $r$ too. Thus any common divisor of $U$ and $V$ also divides $V$ and $r$.

Conversely, if $k$ divides $V$ and $r$, write $V = kn$ and $r = ks$. Then $U = qV + r = qkn + ks = k(qn + s)$, so $k$ divides $U$. We have proved both directions: the common divisors of the two pairs are exactly the same. At the end the pair is $(d, 0)$. Every positive divisor of $d$ also divides 0, because $0 = k \times 0$. The greatest of these is $d$ itself. Since no replacement changed the common divisors, this $d$ is also $\gcd(a, b)$.

Why can $d$ always be written using $a$ and $b$?

At the beginning, $a = 1a + 0b$ and $b = 0a + 1b$ already have the required form. Suppose the two numbers at some stage are $U = ma + nb$ and $V = pa + sb$, with integer coefficients. The next remainder is their integer combination $U - qV$. Expand it to see what happens to the coefficients.

The new coefficients $m - qp$ and $n - qs$ are integers because sums and products of integers remain integers. So the required form is preserved at every step. The final $d$ is one of the numbers retained during this process. It may be an original number if the first division is exact, or a later remainder. Both cases have the required form, so there are integers $u$ and $v$ such that $au + bv = d$. Reading the divisions backwards computes these coefficients, as we did for 3 and 5. This statement is often called Bézout’s identity; the name comes after the argument, not in place of it.

If $d$ divides $c$, then $k = c/d$ is an integer. The last equation constructs an integer solution $x = ku, y = kv$. We have now proved sufficiency as well as necessity: for positive integers $a$ and $b$, $ax + by = c$ has integer solutions if and only if $\gcd(a, b)$ divides $c$. ‘If and only if’ means that each statement implies the other. It does not promise nonnegative solutions.

For $6x + 9y = 30$, division gives $9 = 1 \times 6 + 3$ and $6 = 2 \times 3 + 0$. Backwards, $3 = 9 - 6$. Multiply by 10 because $30/3 = 10$: $30 = 10 \times 9 - 10 \times 6 = 6 \times (-10) + 9 \times 10$. Hence $(-10, 10)$ is one solution. In contrast, no integer scaling of 3 gives 31, exactly as our necessary-condition argument predicted.

Return to $3x + 5y = 29$ and the solution (3, 4). Increasing $x$ by 5 adds $3 \times 5 = 15$ to the total. Decreasing $y$ by 3 removes $5 \times 3 = 15$. The two changes cancel, so (8, 1) is another solution. Reversing the move gives $(-2, 7)$. Repeating a whole number of moves suggests $x = 3 + 5t$ and $y = 4 - 3t$, where $t$ may be any integer, including a negative one or zero.

Substitution proves that every pair we generate works. But could there be another solution that this rule never reaches? To answer that, begin with an arbitrary integer solution $(x, y)$, meaning any solution at all, not one selected from our list. Subtract the known equality $3 \times 3 + 5 \times 4 = 29$ from its equality $3x + 5y = 29$.

The symbol $\Delta$ names a change: $\Delta x$ is $x - 3$, not a new multiplication. We need to show that $\Delta x$ is a multiple of 5. We cannot just cancel a 3 from a divisibility claim without a reason. Use the identity $2 \times 3 - 5 = 1$ that we derived above. Multiply it by $\Delta x$, then use $3\Delta x = -5\Delta y$.

The expression in parentheses is an integer, so $\Delta x = 5t$ for some integer $t$. Substitute this into $3\Delta x = -5\Delta y$: $15t = -5\Delta y$. Divide by the nonzero number $-5$ to get $\Delta y = -3t$. Thus the arbitrary solution must have $x = 3 + 5t$ and $y = 4 - 3t$. We proved both jobs: every generated pair is a solution, and every integer solution is generated. That is a complete solution.

Repeat the argument with general coefficients

Suppose $a > 0$, $b > 0$ and $d = \gcd(a, b)$ divides $c$. Let $(x_{0}, y_{0})$ be one integer solution; the small zero is only a label for our starting solution. Write $A = a/d$ and $B = b/d$. These are positive integers. They have no common positive divisor larger than 1: if $h$ divided both, $dh$ would divide both $a$ and $b$; for $h > 1$ this would give $dh > d$, contradicting the definition of $d$ as the greatest common divisor. We say $A$ and $B$ are coprime.

We divided by $d$ to obtain the last line, which is allowed because $d > 0$. Since $A$ and $B$ are coprime, the Euclidean argument gives integers $u$, $v$ with $uA + vB = 1$. Multiply by $\Delta x$. The term $A\Delta x$ can be replaced by $-B\Delta y$, so both terms then contain $B$.

Therefore $\Delta x = Bt$ for some integer $t$. Substitution into $A\Delta x = -B\Delta y$ gives $ABt = -B\Delta y$. Since $B > 0$, divide by $B$ and get $\Delta y = -At$. Conversely, these changes always cancel: $a(Bt) + b(-At) = (ab/d)t - (ba/d)t = 0$. We have again proved both directions, so all integer solutions are exactly the following.

This also explains why we may choose a convenient starting solution. From the Euclidean solution $(58, -29)$ for the pack equation, taking $t = -11$ gives $x = 58 + 5 \times (-11) = 3$ and $y = -29 - 3 \times (-11) = 4$. Starting from (3, 4) then labels the same solutions with a shifted parameter. For $6x + 9y = 30, d = 3$, so the move is $(9/3, -6/3) = (3, -2)$. From $(-10, 10)$, four moves give $(-10 + 12, 10 - 8) = (2, 2)$.

In the next model, the horizontal coordinate is $x$ and the vertical coordinate is $y$. Green dots are integer solutions; the amber ring marks the selected one. Choose an equation, then change $t$ by a whole step. The dashed right-angle path shows the change in $x$ first and the change in $y$ second, while the arithmetic verifies that the total stays fixed. Try the target 31 too: the impossibility is arithmetic, not a point hidden outside the drawing.

The complete integer answer to $3x + 5y = 29$ is $x = 3 + 5t, y = 4 - 3t$. Our packs require $x \ge 0$ and $y \ge 0$ as well. We therefore impose both inequalities on the same parameter $t$, not on two independently chosen numbers.

In the first line we subtracted 3 and divided by positive 5, so the inequality direction did not change. In the second we added $3t$ to both sides, then divided by positive 3. Combining them gives $-3/5 \le t \le 4/3$. Because $-1 < -3/5 < 0$ and $1 < 4/3 < 2$, the only integers in this interval are 0 and 1.

Thus our two choices are exactly (3, 4) and (8, 1). ‘Exactly’ is justified twice now: we checked all nonnegative $x$ values earlier, and we have just restricted a proven complete integer solution. A competition answer should make that completeness visible, rather than stop after listing two successful guesses.

For a reusable form, let $\lceil r\rceil$ mean the smallest integer at least $r$, and let $\lfloor r\rfloor$ mean the greatest integer at most $r$. These are definitions of rounding upwards and downwards on the number line. For example, $\lceil -3/5\rceil = 0$ because 0 is the first integer to its right, while $\lfloor 4/3\rfloor = 1$ because 1 is the last integer to its left. With $A = a/d > 0$ and $B = b/d > 0$, the two nonnegative conditions become the following.

If the lower integer bound exceeds the upper one, there is no nonnegative solution, even though integer solutions may exist. For instance, $3x + 5y = 1$ has the integer solution $(2, -1)$, because $6 - 5 = 1$. Its full solution is $x = 2 + 5t, y = -1 - 3t$. Nonnegativity requires $t \ge -2/5$, hence $t \ge 0$, and $t \le -1/3$, hence $t \le -1$. No integer meets both. This is why $\gcd(a, b)$ | $c$ alone cannot solve a counting problem.

So far each unknown has been multiplied only by a fixed number. Such equations are linear. Now consider $xy = x + y + 3$ with $x$ and $y$ integers. The product $xy$ makes this a different kind of equation. The previous linear formula does not apply. We need a way to turn the equation into a finite question about integers.

Products suggest factors. Move $x$ and $y$ to the left by subtracting them from both sides: $xy - x - y = 3$. The expression nearly matches $(x - 1)(y - 1)$. We check by multiplying each term, rather than assuming the match: $(x - 1)(y - 1) = xy - x - y + 1$. The missing term is $+1$, so add 1 to both sides of our equation.

Let $u = x - 1$ and $v = y - 1$, so $uv = 4$. Subtracting 1 from an integer gives an integer, and conversely any integer $u$ gives the integer $x = u + 1$. Thus this change of names neither loses nor invents integer pairs. We must find every ordered factor pair of 4; ordered means that the first number supplies $x$ and the second supplies $y$, so exchanging them can give a different solution.

Neither factor can be zero because their product is 4. Their signs must agree: one positive and one negative would give a negative product. If both are positive, each is at least 1, so neither can exceed 4. Test $u = 1, 2, 3$, 4: the matching values $v = 4/u$ are $4, 2, 4/3, 1$. The third is not an integer. If both factors are negative, write $u = -s, v = -r$ with $s$, $r$ positive. Then $uv = sr = 4$, so the negative pairs are precisely the negatives of the three positive pairs.

Select a factor pair below. The display adds 1 to each coordinate and checks both sides of the original equation separately. Because every algebraic step can be reversed and our factor list is complete, these six pairs are all the integer solutions. If the problem had asked for positive $x$ and $y$, we would keep only (2, 5), (3, 3) and (5, 2); the other three contain zero or negative coordinates.

In the rectangle, one cell has side length 1 and area 1. The horizontal label $|u|$ and vertical label $|v|$ give absolute values: the size of each number with any minus sign removed. Thus $|-2| = 2$ and $|2| = 2$. Multiplying these side lengths counts the four cells. For a negative pair, this shows the sizes only; we still check the two negative signs in the arithmetic.

Not every equation becomes a useful product. Consider $x^{2} + y^{2} = 3$ with integer $x$ and $y$. Here $x^{2}$ means $x \times x$. We can test small values, but testing is not the reason there is no solution. Instead, we will show that the left and right sides have incompatible remainders on division by 4. This connects to congruences: saying two integers are congruent modulo 4 means their difference is divisible by 4, equivalently that they leave the same remainder.

Why are those two descriptions equivalent? Write two integers as $4q + r$ and $4s + u$, where $r$ and $u$ are each one of 0, 1, 2, 3. Their difference is $4(q - s) + (r - u)$. Equal remainders make this divisible by 4. Conversely, if it is divisible by 4, then $r - u$ must be a multiple of 4. But $-3 \le r - u \le 3$, and the only multiple of 4 in that range is 0. Thus $r = u$.

Every integer $n$, including a negative one, lies in one block from $4q$ to $4q + 3$ for an integer $q$, so $n = 4q + r$ with $r \in$ {0, 1, 2, 3}. For a precise choice, $q = \lfloor n/4\rfloor$ gives $q \le n/4 < q + 1$; multiply by 4 and subtract $4q$ to obtain $0 \le n - 4q < 4$. For example, $-1 = 4 \times (-1) + 3$. Square each of the four forms and keep track of multiples of 4.

Each expansion uses $(a + b)^{2} = a^{2} + ab + ba + b^{2} = a^{2} + 2ab + b^{2}$, obtained by multiplying the two brackets. Every parenthesis on the right is an integer. Therefore any integer square has remainder 0 or 1 modulo 4. For two squares, the possible remainder sums are $0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1$ and $1 + 1 = 2$. None needs another reduction by 4, and none is 3.

The right side of $x^{2} + y^{2} = 3$ leaves remainder 3. If the two sides were equal integers, their remainders would agree. They cannot, so there is no integer solution. The same calculation rules out any target with remainder 3 modulo 4. The reverse statement is not proved: passing a remainder test is only a necessary condition, just as we carefully distinguished before proving the linear existence theorem.

For each question, decide what a complete answer needs before calculating: a proof of impossibility, one solution plus every possible move, or a complete factor list. The worked answers below are available when you want to compare your reasoning. They do not advance automatically.

What if a coefficient is zero or negative?

We stated $a, b > 0$ in the main proof so that its divisions and nonnegative inequalities were unambiguous. Do not insert zero into a denominator in that proof. If $a = 0$ and $b \ne 0$, the equation is simply $by = c$: $y = c/b$ is allowed only when this quotient is an integer, while $x$ may be any integer. If $b = 0$ and $a \ne 0$, similarly $x = c/a$ must be an integer and $y$ is free. If both are zero, the left side is always zero: every integer pair works when $c = 0$, and none works when $c \ne 0$.

A negative nonzero coefficient can be handled by changing the sign of its unknown. For example, $-3x + 5y = 29$ becomes $3X + 5y = 29$ after defining $X = -x$. Every integer $x$ gives exactly one integer $X$, and the reverse rule is $x = -X$, so integer solutions are preserved. We already know $X = 3 + 5t$ and $y = 4 - 3t$; hence $x = -3 - 5t$. Check: $-3(-3 - 5t) + 5(4 - 3t) = 9 + 15t + 20 - 15t = 29$. If there are nonnegative restrictions, translate them too: $x \ge 0$ means $X \le 0$, not $X \ge 0$.

We can now make the connection without introducing an unexplained new method. In linear algebra, a pair of numbers can be written as a column. We call such a column a vector here. Adding two columns means adding their first entries and adding their second entries. Multiplying a column by a number means multiplying each entry. These operations describe the same coordinate moves we have already used.

For $6x + 9y = 30$, start at (2, 2). The column $(3, -2)$ describes a move: add 3 to the first coordinate and subtract 2 from the second. The equation checks a pair by multiplying its first entry by 6 and its second by 9, then adding. We can write that operation using a row [6 9], called a one-row matrix. The following multiplication is its definition here.

Before using matrix notation for a sum, let us expand the ordinary arithmetic inside it. Write the two entries of a column $p$ as $p_{1}$ and $p_{2}$, and those of another column $z$ as $z_{1}$ and $z_{2}$. The small labels 1 and 2 mean first and second positions, not powers. Adding the columns gives entries $p_{1} + z_{1}$ and $p_{2} + z_{2}$. Now multiply the first by 6 and the second by 9.

For subtraction the same expansion gives $6(w_{1} - p_{1}) + 9(w_{2} - p_{2}) = 6w_{1} - 6p_{1} + 9w_{2} - 9p_{2} = (6w_{1} + 9w_{2}) - (6p_{1} + 9p_{2})$, which we write as $M(w - p) = Mw - Mp$. Thus the compact matrix rules below come from the distributive law we have just used, rather than a new assumption.

The move contributes zero to the total, which is why it can be added to a solution. More generally, if $p$ is one column with $Mp = c$ and $z$ is a column with $Mz = 0$, distributing ordinary multiplication gives $M(p + z) = Mp + Mz = c + 0 = c$. Conversely, if $w$ is any other column with $Mw = c$, subtract the first equality: $M(w - p) = Mw - Mp = c - c = 0$. Thus every solution is one particular solution plus a move whose output is zero.

Let us draw that subtraction before giving the collection of moves a name. Keep the starting solution (2, 2) fixed. In step 1 below, choose a point on $6x + 9y = 30$. In step 2, subtract 2 from its horizontal coordinate and 2 from its vertical coordinate. The same subtraction is applied to every displayed point. Watch the starting solution become the origin, and compare the unchanged coordinate differences.