# Linear Diophantine Equations

A Diophantine equation is an equation whose solutions are restricted to integers. In a **linear Diophantine equation**, the equation is a polynomial in which all of the monomials have degree zero or one. The simplest non-trivial linear Diophantine equation is

\[ ax + by = c\]

for integers \(a,b\), and \(c\). As we saw in Bézout's Identity, this equation has integer solutions \(x,y\) if and only if \(c\) is a multiple of \(\gcd(a,b)\). Furthermore, the set of all solutions of the equation can be described as follows:

If \(\left(x^*,y^*\right)\) is an integer solution of the Diophantine equation \( ax + by = c,\) then all integer solutions to the equation are of the form

\[ \left(x^* + m \frac{b}{\gcd(a,b)}, ~~ y^* - m \frac{a}{\gcd(a,b)}\right) \]

for some integer \(m\). \(_\square\)

Proof:We have

\[ \begin{align} a \left( x^* + m \frac{b}{\gcd(a,b)} \right) + b \left( y^* - m \frac{a}{\gcd(a,b)} \right) &= ax^* + by^* + \frac{ a b m}{\gcd(a,b)} - \frac{abm}{\gcd(a,b)} \\ &= ax^* + by^* \\ & = c, \end{align}\]

which shows these are indeed solutions to the Diophantine equation. Now, given any solution \( (x, y) \), we have

\[\begin{align} ax + by &= ax^* + by^* \\ a(x - x^*) &= -b(y - y^*) \\ \frac{a}{\gcd(a,b)} (x - x^*) &= - \frac{b}{\gcd(a,b)} (y-y^*) . \end{align}\]

Since \(\frac{a}{\gcd(a,b)}\) and \(\frac{b}{\gcd(a,b)}\) are relatively prime, there exists an integer \(m\) such that \(x-x^* = m \frac{b}{\gcd(a,b)} \) and \(y-y^* = -m \frac{a}{\gcd(a,b)},\) proving the theorem. \(_\square\)

Now, consider the linear Diophantine equation in three variables \(ax + by + cz = d.\) Again by Bézout's Identity, as \(a\) and \(b\) range over all integer values, the set of values \(ax + by\) is equal to the set of multiples of \(\gcd(a,b).\) This shows that the Diophantine equation \(ax+by+cz=d\) has integer solutions if and only if \(\gcd(a,b)w+cz=d\) has integer solutions, for \(ax+by=\gcd(a,b)w.\) By the above reasoning, the second equation has integer solutions if and only if \( \gcd(a,b,c)\) divides \(d.\)

By continuing this argument, the linear Diophantine equation

\[a_1x_1 + a_2x_2 + \cdots + a_kx_k=d \]

has an integer solution \( (x_1, x_2, \ldots, x_k) \) if and only if \(\gcd(a_1,a_2, \ldots, a_k) \) divides \(d\).

In some applications, it may be of interest to find the **positive** (or nonnegative) integer solutions of the Diophantine equation \( ax + by = c\). For these problems, we would like to find the integer values \(m\) such that the solutions

\[ x^* + m \frac{b}{\gcd(a,b)}, ~~ y^* - m \frac{a}{\gcd(a,b)} \]

are both positive (or both nonnegative).

Find all integers \(c\) such that the linear Diophantine equation \(52x + 39y = c\) has integer solutions, and for any such \(c,\) find all integer solutions to the equation.

In this example, \( \gcd(52,39) = 13.\) Then the linear Diophantine equation has a solution if and only if \(13\) divides \(c\). Thus, the values \(c\) such that the equation has integer solutions are the multiples of \(13\). Now, for any such \(c\), one solution to the Diophantine equation is \( (x^*,y^*) =\left( \frac{c}{13}, - \frac{c}{13} \right) \). Then, the above implies the integer solutions to the equation are

\[ (x,y) = \left( \frac{c}{13} + 3m, ~ - \frac{c}{13} - 4m \right) \]

for \(m\) integer. \(_\square\)

Find the positive integer solutions of the Diophantine equation \(4x + 7y = 97\).

We have \(\gcd(a,b) = \gcd(4,7)=1\) and \(1 = 4 \cdot 2 + 7 \cdot (-1)\). Then one solution is \(x^* = 2 \cdot 97\), \(y^* = (-1) \cdot 97\), and all solutions are of the form

\[\left( x^* + m \frac{b}{\gcd(a,b)}, ~ y^* - m \frac{a}{\gcd(a,b)} \right)\] or \[ \left( 2 \cdot 97+ 7m, ~ -97 - 4m \right) \]

for \(m\) integer. Then we would like to find the integers satisfying \( 2 \cdot 97 + 7m > 0\) and \( -97 - 4m > 0\), or

\[ - \frac{ 2 \cdot 97}{7} < m < - \frac{97}{4} .\]

The integers \(m\) satisfying this equation are \(m=-27, -26, -25,\), which gives the solutions \((5, 11), (12,7 ),\) and \((19,3)\). \(_\square\)

Jack, Charlie and Andrew went on an egg hunt today, each of them carrying one basket. 300 eggs were hidden in the beginning of the day. At the end of the day, the number of eggs in each of the boys' baskets are three consecutive integers. In how many ways could this happen?

**Clarifications**:

Order doesn't matter. For example, in the order of Charlie, Andrew and Jack, \((3,2,1)\) and \((2,3,1) \) count as one way.

Consider 3 positive integers \(x, y,\) and \(z\) satisfying the following equation: \(28x+30y+31z=365\).

What is the value of \(x+y+z\)?

First, looking closely at the equation, we can notice that the coefficients are the number of days in the months and the right hand side of the equation is the number of days in a year.

February is the month with 28 days. There are 4 months in the year with 30 days and 7 months consisting of 31 days.

Hence we get a solution \(x=1, y=4\), and \(z=7\). This would give a solution \(x+y+z=12\).

But, can we find another positive integer solution? By using trial and error method, we can easily prove that all positive integer solutions of the above equation are \((x,y,z)=(1,4,7)\) and \((x,y,z)=(2,1,9)\). Then, \(x+y+z\) is always equal to \(12\).

Surprisingly, we can find the value of \(x+y+z\) without solving the above equation.

Indeed, because \(x,y,z\) are positive integers, we have

\[\begin{align} 28(x+y+z)=365-2x-3z &\le365-2\cdot1-3\cdot1=360\\ x+y+z &\le\dfrac{360}{28}\\&=12\dfrac{6}{7}\\\\ 31(x+y+z)=365+3x+y &\ge365+3\cdot1+1=369\\ x+y+z &\ge\dfrac{369}{31}\\&=11\dfrac{28}{31}. \end{align}\]

On the other hand, \(x+y+z\) is a integer number, so \(x+y+z=12.\ _\square\)

For more on linear Diophantine equations, see Linear Diophantine Equations.

**Cite as:**Linear Diophantine Equations.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/linear-diophantine-equations-one-equation/