3.5 Linear Diophantine Equations

Find the general solution to \[1815x+1415y=-10,\] Equations in one or more variables, for which we seek integer-valued solutions.

Simplest example is the linear Diophantine equation \[ax+by=c\] The following result was known to the Indian mathematician Brahmagupta, around 628 AD:

Theorem 3.31

Let \(a, b\) and \(c\) be integers, with \(a\) and \(b\) not both \(0\), and let \(d=\gcd(a, b)\). Then the equation \[ax+by=c\] has an integer solution \(x, y\) if and only if \(c\) is a multiple of \(d\), in which case there are infinitely many solutions.

Writing \(a=pd\) and \(b=qd\) the solutions are

\[x=x_0+{qn},\quad y=y_0-{pn}\qquad(n\in{\mathbb Z }),\]

where \(x_0, y_0\) is any particular solution.

Proof. The fact that there is a solution if and only if \(d|c\) is simply a restatement of Theorem 3.16.

To find the general form of the solutions, let \(x_0, y_0\) be a particular solution, so \(ax_0+by_0=c.\)

Let \(n\in\mathbb Z\) and put \[x=x_0+{qn},\quad y=y_0-{pn}.\] Then \[ax+by=a(x_0+{qn})+b(y_0-{pn})=\] \[ax_0+by_0+(aqn-bpn)=c+(pdqn-qdpn)=c,\] and so \(x, y\) is also a solution. As this holds for an integer \(n\) then there are therefore infinitely many solutions.

Now suppose that \(x, y\) is any integer solution, so that \(ax+by=c\). Since \(ax+by=c=ax_0+by_0\) we have \[a(x-x_0)=b(y_0-y).\]

Now \(a=pd\) and \(b=qd\) and so \[pd(x-x_0)=qd(y_0-y).\] Applying the cancellation lemma to cancel \(d\) we get \[p(x-x_0)=-q(y-y_0).\qquad(*)\] Hence \(q\) is a divisor of \(p(x-x_0)\), and \(p\) is a divisor of \(q(y-y_0)\).

Since \(a\) and \(b\) are not both \(0\), we can suppose that \(b\neq 0\) (otherwise we can interchange the roles of \(a\) and \(b\)). Consequently \(q\ne0\).

We also note that \(q\) is coprime to \(p\) by Corollary 3.26, and so it divides \(x-x_0\) by Corollary 3.27(b). Thus \(x-x_0=qn\) for some integer \(n\) and so \[x=x_0+{qn}.\]

Substituting back for \(x-x_0\) in \((*)\) we get \[-q(y-y_0)=p(x-x_0)=pqn,\]

Since \(q\neq 0\) the Cancellation Lemma implies that \[y=y_0-pn.\]

Thus we can find the solutions of any linear Diophantine equation \(ax+by=c\) by the following technique:

  • Calculate \(d=\gcd(a, b)\), either directly or by Euclid’s algorithm.
  • Check whether \(d\) is a divisor of \(c\): if it is not, there are no solutions, so stop here; if it is, write \(c=de\).
  • If \(d|c\), use the method of proof of Theorem 3.16 to find integers \(u\) and \(v\) such that \(au+bv=d\); then \(x_0=ue, y_0=ve\) is a particular solution of \(ax+by=c\).
  • Use Theorem 3.31 to find the general solution \(x, y\) of the equation.
Example 3.32

Find the general solution to \[1815x+1415y=-10,\] so \(a=1815,\; b=1415\) and \(c=-10\).

In step (1), we use Example 3.13 to see that \(d=5\).

In step (2) we check that \(d\) divides \(c\): in fact, \(c=-2d\), so \(e=-2\).

In step (3) we use Example 3.20 to write \(d=46\times1815+(-59)\times1415\); thus \(u=46\) and \(v=-59\),

so \(x_0=46\times(-2)=-92\) and \(y_0=(-59)\times(-2)=118\) give a particular solution of the equation.

By Theorem 3.31, the general solution has the form

\[x=-92+\frac{1415n}{5}=-92+283n,\quad y=118-\frac{1815n}{5}=118-363n \]

\[n\in{\mathbb Z }.\]