Diophantine Equations (of the Linear Kind)

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

We solve linear Diophantine equations over the integers. In the two variable case, we provide a complete solution using the Euclidean Algorithm. Also, we will discuss the multi-variable case and provide examples.

We will take note of the fact that a Diophantine Equation of the linear kind seeks to equate the sum of two or more monomials, with at least one variable being of degree 1, to a constant. Again, the solutions to such equations are closely linked to modular arithmetic discussed earlier.

Introduction

In the following Diophantine equations, $x$, $y$, and $z$ are the unknowns and the other letters are given constants. $$ax+by=1$$ This is a linear Diophantine equation. $$x^n+y^n=z^n$$ For $n = 2$ there are infinitely many solutions $(x,y,z)$: the Pythagorean triples. For larger integer values of $n$, Fermat’s Last Theorem states there are no positive integer solutions $(x, y, z)$. $$x^2-ny^2=\pm 1 $$ This is Pell’s equation, which is named after the English mathematician John Pell. It was studied by Brahmagupta in the 7th century, as well as by Fermat in the 17th century. $$ \frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}$$

The Erdos-Straus conjecture states that, for every positive integer $n > 2$, there exists a solution in $x, y,$ and $z,$ all as positive integers. Although not usually stated in polynomial form, this example is equivalent to the polynomial equation $$ 4xyz = yzn + xzn + xyn = n(yz + xz + xy).$$

The term Diophantine equation usually refers to any equation in one or more unknowns that is to be solved in the integers.

The simplest kind of Diophantine equation is the linear Diophantine equation, namely $a x + b y = c$. In general, Diophantine equations furnish a natural vehicle for puzzles and problems of a mathematical nature.

Two Variable Linear Diophantine Equations

Linear Diophantine Equations with two variables present interesting results. With two unknowns, they tend to have infinitely many solutions in the homogeneous case. However, their construction makes it easier to employ the Euclidean Algorithm, hence are easier to solve. Remember, cases may arise where the equation does not have proper solutions.

Theorem. (Linear Diophantine Equation) The linear Diophantine equation $a x+b y=c$ has a solution if and only if $d|c,$ where $d=(a,b).$ Moreover, if $\left(x_0,y_0\right)$ is a solution, then the set of solutions of the equation consists of pairs $(x,y)$ where \begin{equation*} x=x_0+\frac{t b}{d} \qquad \text{and} \qquad y=y_0-\frac{t a}{d} \end{equation*} and $t$ is an arbitrary integer.

Proof. Since $d=(a,b)$ there exists integers $m$ and $n$ such that $a m+b n=d$. Since $d|c$ we have an integer $k$ such that $c=d k$ and thus we have $(a m+b n)k=d k$. Thus, $a (m k)+b (n k)=c$ and so we have a solution.

Conversely, suppose $a x+b y=c$ has a solution say $x_1$ and $y_1.$ Then $a x_1+b y_1=c$ and since $d|a$ and $d|b$ we have $d|c.$ Let $x_0$ and $y_0$ be any solution. Then we have $a x_0+b y_0=c$ and so $$ a x_0+\frac{t a b}{d}+b y_0-\frac{t a b}{d}=c $$ for any integer $t$ as needed.

It remains to show that all solutions $(x,y)$ have the correct form. Let $(x,y)$ be an arbitrary solution and let $\left(x_0,y_0\right)$ be any particular solution. Then we have $a\left(x-x_0\right)+b\left(x-x_0\right)=0$ and thus $a\left(x-x_0\right)=b\left(y_0-y\right).$ Now enter $d$. Dividing by $d,$ we have $$\frac{a}{d}\left(x-x_0\right)=\frac{b}{d}\left(y_0-y\right). $$ Observe that $$ \left(\frac{a}{d},\frac{b}{d}\right)=1 $$ and so $\frac{a}{d}\mid \left(y_0-y\right)$. Therefore, there exists an integer $s$ such that $y=y_0-\left(\frac{a}{d}\right)s$ and by substitution, $x=x_0+\left(\frac{b}{d}\right)s$ as desired.

Solving Linear Diophantine Equations

While solving linear Diophantine equations is a straightforward process, this is not true for general Diophantine equations. In 1900, in recognition of their depth, David Hilbert proposed the solvability of all Diophantine problems as the tenth of his celebrated problems. In 1970, a novel result in mathematical logic known as Matiyasevich‘s theorem settled the problem negatively: in general, Diophantine problems are unsolvable.

We can check if a linear Diophantine equations is solvable and if so, actually find its solutions. The key ingredient in finding a particular solution is the Euclidean algorithm.

Example. Solve the linear Diophantine equation $14x+34y=90.$

Solution. Since $(14,34)=2$ and $2|90.$ There is a solution and so we need to find an initial solution. Since an initial solution is $x=4$ and $y=1$ we have all solutions $x=4+17 t $ and $y=1-7 t$ where $t\in\mathbb{Z}$.

Example. Solve the linear Diophantine equation $14x+35x=91.$

Solution. Since $(14,35)=7$ and $7|91$ the equation is solvable. Since an initial solution is $x=4$ and $y=1$ we have all solutions $x=4+2t$ and $y=1-5t$ where $t\in\mathbb{Z}$.

Example. Solve the linear Diophantine equation $14x+36y=93.$

Solution. Since $(14,36)=2$ and $2\nmid 93$ there are no solution to the linear Diophantine equation $14x+36y=93.$.

Diophantine Equations

Special Case

However, in this article, we will explore a simpler problem of special case Diophantine Equation of the linear type. Here, the solution to the problem is expressed as arbitrary integral values of a given constant. See the corollary below.

Corollary. If $(a,b)=1$ and if $x_0$ and $y_0$ is a particular solution of the linear Diophantine equation $a x+b y=c,$ then all solutions are given by $x=x_0+b t$ and $y=y_0-a t$ for integral values of $t.$

Proof. The proof follows immediately from the Theorem above.

For example, the equation $5x+22y=18$ has $x_0=8,$ $y_0=-1$ as one solution and so a complete solution is given by $x=8+22t$ and $ y=-1-5t$ for arbitrary integral values of $t.$

Multivariables Equations

A problem in Diophantus’ Arithmetica is to find four natural numbers whose sums by three are 20, 22, 24, and 27. Can you find these four integers?

Diophantus made important advances in mathematical notation, becoming the first person known to use algebraic notation and symbolism. Note that before him everyone wrote out equations completely. Furthermore, Diophantus introduced an algebraic symbolism that used an abridged notation for frequently occurring operations, and an abbreviation for the unknown and for the powers of the unknown.

Theorem. (General Linear Diophantine Equation) If $a_1,a_2,\ldots , a_n$ are nonzero positive integers, then the equation $$ a_1x_1+ \cdots + a_nx_n = c$$ has an integral solution if and only if $d=\left(a_1,\ldots , a_n\right)$ divides $c.$ Furthermore, when there is a solution, there are infinitely many solutions.

Example. Which combinations of pennies, dimes, and quarters have a total value of $99$ cents?

Solution. Let $x,y,$ and $z$ be the number of pennies, dimes, and quarters, respectively. To solve this question, we will solve the linear Diophantine equation: $x+10y+25z=99.$ Since $x,y,$ and $z$ are all positive integers, it follows that $z=0,1,2,3;$ and so we can solve the 4 corresponding equations in only $x$ and $y.$ First, we solve $x+10y=99.$ Clearly, $x_0=99$ and $y_0=0$ is a particular solution and since $(1,10)=1$ all solutions are given by $x=99+10t$ and $y=0-t.$ By letting $t$ range from 0 to $-9$, we find some combinations of pennies, dimes, and quarters that total 99 cents: $$\begin{array}{c|cccccccccc} x & 99 & 89 & 79 & 69 & 59 & 49 & 39 & 29 & 19 & 9 \\ \hline y & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline z & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline t & 0 & -1 & -2 & -3 & -4 & -5 & -6 & -7 & -8 & -9 \end{array}$$

Applications of Linear Diophantine Equations

Continuing, we solve $x+10y=74.$ Clearly, $x_0=74$ and $y_0=0$ is a particular solution and since $(1,10)=1$ all solutions are given by $x=74+10t$ and $y=0-t.$ By letting $t$ range from 0 to $-7$, we find more combinations of pennies, dimes, and quarters that total 99 cents: $$ \begin{array}{c|cccccccc} x & 74 & 64 & 54 & 44 & 34 & 24 & 14 & 4 \\ \hline y & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline z & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline t & 0 & -1 & -2 & -3 & -4 & -5 & -6 & -7 \end{array} $$

Next, we solve $x+10y=49.$ Clearly, $x_0=49$ and $y_0=0$ is a particular solution and since $(1,10)=1$ all solutions are given by $x=49+10t$ and $y=0-t.$ By letting $t$ range from 0 to $-4$, we find more combinations of pennies, dimes, and quarters that total 99 cents: $$ \begin{array}{c|ccccc} x & 49 & 39 & 29 & 19 & 9 \\ \hline y & 0 & 1 & 2 & 3 & 4 \\ \hline z & 2 & 2 & 2 & 2 & 2 \\ \hline t & 0 & -1 & -2 & -3 & -4 \end{array} \hspace{1cm} \begin{array}{c|ccc} x & 24 & 14 & 4 \\ \hline y & 0 & 1 & 2 \\ \hline z & 2 & 2 & 2 \\ \hline t & 0 & -1 & -2 \end{array} $$ Finally, we solve $x+10y=24.$ Clearly, $x_0=24$ and $y_0=0$ is a particular solution and since $(1,10)=1$ all solutions are given by $x=49+10t$ and $y=0-t.$ By letting $t$ range from 0 to $-2$, we find even more combinations of pennies, dimes, and quarters that total 99 cents.

Exercises on Linear Diophantine Equations

Exercise. Solve the linear Diophantine equation by either finding all solutions or by showing there are none.

$(1) \qquad 3x+4y=7$

$(2) \qquad 17x+13y=100$

$(3) \qquad 30x+47y=-11$

$(4) \qquad 25x+95y=970$

$(5) \qquad 102x+1001y=1$

$(6) \qquad 7x+21 y+35z=8$

$(7) \qquad 6x+51y=22$

$(8) \qquad 33x+14y=115$

$(9) \qquad 14x+35y=93$

$(10) \qquad 56x+72y=40$

$(11) \qquad 24x+138y=18$

$(12) \qquad 221x+35y=11$

$(13) \qquad 18x+5y=48$

$(14) \qquad 54x+21y=906$

$(15) \qquad 158x-57y=7$

$(16) \qquad 41x-51y=223$

Exercise. Solve the linear Diophantine equation $7101x+102y+103z=1$ by either finding all solutions or by showing there are none.

Exercise. A grocer order apples and oranges at a total cost of $\$ 8.39.$ If apples cost him $25$ cents each and oranges cost him 18 cents each, how many of each type of fruit did he order?

Exercise. A postal clerk has only $14$ cents and $21$ cent stamps to sell. What combination of these may be used to mail a package requiring postage
of exactly \$$4.00.$

Exercise. Divide 100 into two summands such that one is divisible by 7 and the other by 11.

Exercise. Is it possible to have 50 coins, all of which are pennies, dimes, or quarters, with a total worth 3 dollars.

More Exercises on Linear Diophantine Equations

Exercise. When Mr. Smith cached a check at his bank, the teller mistook the number of cents for the number of dollars and vice versa. Unaware of this, Mr. Smith spent 68 cents and then noticed, to his surprise, that he had twice the amount of the original check. Determine the smallest value for which the check could have been written.

Exercise. Divide 100 into two summands such that one is divisible by 7 and the other by 11.

Exercise. A man has 5 diamonds, 8 rubies, 7 sapphires, and 83 gold coins; a second man has 7,9,6, and 74 of these items, respectively; a third man has 3, 13, 11, and 80. If the collections are considered equally valuable, how many gold coins is each diamond, ruby, and sapphire writ?

Exercise. Solve the linear Diophantine equation, $714x+7007y=7.$

Exercise. Solve the linear Diophantine equation by either finding all solutions or by showing there are none for $17x+13y=100.$

Exercise. Solve the linear congruence $5x\equiv 7 \pmod{57}$ using basic properties of congruence (no linear Diophantine equation). Show all your steps.

Exercise. Explain why the linear Diophantine equation $2x-101y=82$ is solvable or not solvable.
If possible find all solutions.

Exercise. Solve the linear congruence $5x\equiv 15 \pmod{35}$ by solving a linear Diophantine equation. Show all your steps.

Exercise. Solve the congruence $3x\equiv 5 \pmod{16}$ by writing a linear Diophantine equation and solving it.