Number Theory Primer : The Diophantine Equation ax + by = c

authored by Premmi and Beguène

Previous Topic: The Euclidean Algorithm

Introduction

A Diophantine equation is any equation in one or more unknowns that is to be solved in the integers.

The simplest type of Diophantine equation that we shall consider is the linear Diophantine equation in two unknowns:

ax + by = c

where a, b, c are given integers and a, b are not both zero.

A solution of this equation is a pair of integers x_0, y_0 that, when substituted into the equation, satisfy it; that is, we ask that ax_0 + by_0 = c.

Diophantine equations frequently arise when solving certain types of problems, for example, while solving linear congruences, which we will encounter later during our study of modular arithmetic.

Motivation

Let us motivate a discussion on Diophantine equations through a problem posed by Euler in 1770.

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

Framing this problem in terms of an equation leads us to the following Diophantine equation,

7x + 11y = 100

where 7x is divisible by 7 and 11y by 11 and consequently, x \text{ and } y are positive integers.

In order to find a solution to this problem we need to know whether this equation is solvable. Also, if the equation has a solution, we would like to how many solutions the equation has and what they are.

We will next discuss how to arrive at answers to these questions.

Intuition

The equation 7x + 11y = 100 is a specific instance of the Diophantine equation of the form ax + by = c, wherea = 7, b = 11 \text{ and } c = 100.

As usual, we will find a solution to this problem by relating it to something we already know. We have already encountered an equation of this form during our study of the greatest common divisor of two integers. We have seen that given two integers a \text{ and } b not both of which are zero, there exist integers x^\prime \text{ and } y^\prime such that ax^\prime + by^\prime = d, where d = \text{gcd}(a, b).

Suppose c is some multiple of d i.e., c = dr, where r is an integer.

If we multiply the equation ax^\prime + by^\prime = d with r, we get

arx^\prime + bry^\prime = dr

Since c = dr,

a(rx^\prime) + b(ry^\prime) = c

We can see that x = rx^\prime \text{ and } y = ry^\prime is a solution of the equation ax + by = c.

Therefore, we can see that a solution to the equation exists whenever d \,|\, c.

We will formalize this observation as a theorem and also derive all possible solutions of this equation, where such solutions exist.

Theorem

The linear Diophantine equation ax + by = c has a solution if and only if d \,|\, c, where d = \text{gcd}(a, b).

First we will prove the following conditional statement.

“If the linear Diophantine equation ax + by = c has a solution, then d \,|\, c, where d = \text{gcd}(a, b).”

Since d = \text{gcd}(a, b), by definition, d \,|\, a \text{ and } d \,|\, b. Therefore, from the definition of the divisibility of integers we know that there exist integers r \text{ and } s for which a = dr\text{ and } b = ds.

If a solution of ax + by = c exists, so that ax_0 + by_0 = c for suitable x_0 \text{ and } y_0, then

c = ax_0 + by_0 = drx_0 + dsy_0 = d(rx_0 + sy_0)

which implies that d \,|\, c.

Now lets prove the converse stated below.

“If d \,|\, c, where d = \text{gcd}(a, b), then there exists a solution to the linear Diophantine equation ax + by = c.”

Since d \,|\, c, from the definition of the divisibility of integers c = dt, for some integer t.

Also, since d = \text{gcd}(a, b), from this theorem we know that there exist integers x_0 \text{ and } y_0 such that d = ax_0 + by_0.

When we multiply this relation by t, we get

dt = (ax_0 + by_0)t = a(tx_0) + b(ty_0)

Since c = dt,

a(tx_0) + b(ty_0) = c

Hence, the Diophantine equation ax + by = c has x = tx_0 \text{ and } y = ty_0 as a particular solution.

How do we find all the other solutions to the Diophantine equation ax + by = c ?

Let us suppose that a solution x_0, y_0 of the given equation is known.

If x^\prime, y^\prime is any other solution, then

ax_0 + by_0 = c = ax^\prime + by^\prime

which is equivalent to,

a(x_0 - x^\prime) = b(y^\prime - y_0)

Substituting a = dr \text{ and } b = ds in the above equation, we get

dr(x_0 - x^\prime) = ds(y^\prime - y_0)

Cancelling the common factor d, we get

r(x_0 - x^\prime) = s(y^\prime - y_0)

From the definition of the divisibility of integers, the above equation implies that r \,|\, s(y^\prime - y_0).

Also, the equations a = dr \text{ and } b = ds can be rewritten as r = \dfrac{a}{d} \text{ and } s = \dfrac{b}{d}.

From corollary 1 of a theorem we have already proved, we know that \text{gcd}\bigg(\dfrac{a}{d}, \dfrac{b}{d}\bigg) = 1. Therefore, \text{gcd}(r, s) = 1.

From Euclid’s Lemma we know that r \,|\, (y^\prime - y_0) since r \,|\, s(y^\prime - y_0) and \text{gcd}(r, s) = 1.

From the definition of the divisibility of integers, this implies that y^\prime - y_0 = rt for some integer t.

Substituting the value of y^\prime - y_0 in the above equation, we get

r(x_0 - x^\prime) = srt

which is equivalent to

x_0 - x^\prime = st

This leads us to the formulas

\begin{equation*} 
\begin{split}
x^\prime = x_0 - st &= x_0 - \bigg(\frac{b}{d}\bigg)t \\
y^\prime = y_0 + rt &= y_0 + \bigg(\frac{a}{d}\bigg)t \\
\end{split}
\end{equation*}

It is easy to see that these values satisfy the Diophantine equation, regardless of the choice of the integer t; for

\begin{equation*} 
\begin{split}
ax^\prime + by^\prime &= a \Bigg[x_0 - \bigg(\frac{b} {d}\bigg)t\Bigg] + b\Bigg[y_0 + \bigg(\frac{a}{d}\bigg)t\Bigg]\\
&= (ax_0 + by_0) + \bigg(\frac{ab}{d} - \frac{ab}{d}\bigg)t \\
&= c + 0 \cdot t \\
&= c \\
\end{split}
\end{equation*}

Thus, there are an infinite number of solutions of the given equation, one for each value of t.

Summary

The linear Diophantine equation ax + by = c has a solution if and only if d \,|\, c, where d = \text{gcd}(a, b). If x_0, y_0 is any particular solution of this equation, then all other solutions are given by

x = x_0 - \bigg(\frac{b}{d}\bigg)t \quad \quad\quad y = y_0 + \bigg(\frac{a}{d}\bigg)t

where t is an arbitrary integer.

Example of an application of the theorem

We are now poised to solve the question posed by Euler in 1770, namely, dividing 100 into two summands such that one is divisible by 7 and the other by 11.

The solution to this problem can be framed in terms of a Diophantine equation as given below.

7x + 11y = 100

where x \text{ and } y are some positive integers.

First let us check whether this equation is solvable. From the theorem we have just proved, we know that this equation has a solution if \text{gcd}(7, 11) divides 100.

In this case, since 7 \text{ and } 11 are prime numbers, finding their greatest common divisor is quite straightforward; we know that their only common divisor is 1 and hence, \text{gcd}(7, 11) = 1.

However, we will still use Euclidean Algorithm to find \text{gcd}(7, 11) since we will need the steps in this algorithm to express \text{gcd}(7, 11) as a linear combination of 7 \text{ and } 11, which in turn will help us find the values of x \text{ and } y.

Since \text{gcd}(7, 11) = \text{gcd}(11, 7) and the Euclidean Algorithm requires the first operand to be greater than or equal to the second we will evaluate, \text{gcd}(11, 7).

Applying the Euclidean Algorithm to the evaluation of \text{gcd}(11, 7), we find that

\begin{equation*} 
\begin{split}
11 &= 2 \times 7 - 3\\
7 &= 2 \times 3 + 1\\
3 &= 3 \times 1 + 0\\
\end{split}
\end{equation*}

and therefore, \text{gcd}(11, 7) = 1. Since 1 \,|\, 100, a solution to this equation exists.

To obtain 1 as a linear combination of 11 \text{ and } 7, we work backward through the previous calculations, as follows:

\begin{equation*} 
\begin{split}
1 &= 7 - (2 \times 3)\\
&= 7 - [2 \times (2 \times 7 - 11)]\\
&= 7 - (2 \times 2 \times 7 ) + 2 \times 11 \\
&= 7 (1 - 4) + 2 \times 11 \\
&= 7 (-3) + 11 \times 2\\
\end{split}
\end{equation*}

Therefore,

7 (-3) + 11 \times 2 = 1

Multiplying this equation by 100, we get

\begin{equation*} 
\begin{split}
100[7 (-3) + 11 \times 2] &= 100\\
\end{split}
\end{equation*}

which is equivalent to,

7(-300) + 11 \times 200 = 100

Hence, x = -300 \text{ and } y = 200 is one solution to the Diophantine equation in question.

All other solutions can be expressed by

\begin{equation*} 
\begin{split}
x &= -300 - \bigg(\frac{11}{1}\bigg)t = -300 - 11t \\
y &= 200 + \bigg(\frac{7}{1}\bigg)t = 200 + 7t\\
\end{split}
\end{equation*}

for some integer t.

Since we want to express 100 as a sum of two positive integers, we want the solution in positive integers.

From the above relations we can see that for x \text{ and } y to be positive, t must be chosen to satisfy simultaneously the following inequalities:

-300 - 11t > 0 \quad \quad \quad 200 + 7t > 0

Multiplying the inequality -300 - 11t > 0 with -1, we get

300 + 11t < 0

Adding -300 to both sides of the inequality results in

11t < -300

Dividing both sides of the inequality by 11, we get

t < \frac{-300}{11}

which is equivalent to,

t < -27\frac{3}{11}

Similarly, adding -200 to both sides of the inequality 200 + 7t > 0, we get

7t > -200

Dividing both sides of the inequality by 7, we get

t > \frac{-200}{7}

which is equivalent to,

t > -28\frac{4}{7}

Therefore,

-27\frac{3}{11} > t > -28\frac{4}{7}

Since t must be an integer, we are forced to conclude that t = -28.

Substituting this value of t in the following equations, we get

\begin{equation*} 
\begin{split}
x &= -300 - 11t =-300 - (11 \times -28) = -300 + 308 = 8  \\
y &= 200 + \bigg(\frac{7}{1}\bigg)t = 200 + 7t = 200 + (7 \times -28) = 200 - 196 = 4\\
\end{split}
\end{equation*}

Thus, our Diophantine equation has a unique positive solution x = 8, y = 4 corresponding to the value t = -28.

Therefore, 7x = 7 \times 8 = 56 \text{ and } 11y = 11 \times 4 = 44 are the two numbers that sum to 100 such that 56 is divisible by 7 and 44 by 11.

Diophantine equation ax + by = c, where a and b are relatively prime

As we have seen in the previous example, it might be helpful to record the form that the theorem we have just discussed takes when the coefficients are relatively prime.

Corollary

If \text{gcd}(a, b) = 1 and if x_0, y_0 is a particular solution of the linear Diophantine equation ax + by = c, then all solutions are given by

x = x_0 - bt \quad \quad \quad y = y_0 + at

for integral values of t.