Module 3: Linear Diophantine Equations

Lesson 2 : Finding All Solutions to Linear Diophantine

Equations

Math is Fun!

Diophantus’ Arithmetica
Two works have come down to us under his name, both incomplete. The first is a small
fragment on polygonal numbers (a number is polygonal if that same number of dots can be
arranged in the form of a regular polygon). The second, a large and extremely
influential treatise upon which all the ancient and modern fame of Diophantus reposes, is
his Arithmetica. Its historical importance is two fold: it is the first known work to employ
algebra in a modern style, and it inspired the rebirth of number theory.
The Arithmetica begins with an introduction addressed to Dionysius—arguably St.
Dionysius of Alexandria. After some generalities about numbers, Diophantus explains his
symbolism—he uses symbols for the unknown (corresponding to our x) and its powers,
positive or negative, as well as for some arithmetic operations—most of these symbols are
clearly scribal abbreviations. This is the first and only occurrence of algebraic symbolism
before the 15th century. After teaching multiplication of the powers of the unknown,
Diophantus explains the multiplication of positive and negative terms and then how to reduce
an equation to one with only positive terms (the standard form preferred in antiquity). With
these preliminaries out of the way, Diophantus proceeds to the problems. Indeed,
the Arithmetica is essentially a collection of problems with solutions, about 260 in the part
still extant.
The introduction also states that the work is divided into 13 books. Six of these books
were known in Europe in the late 15th century, transmitted in Greek by Byzantine scholars and
numbered from I to VI; four other books were discovered in 1968 in a 9th-century Arabic
translation by Qusṭā ibn Lūqā. However, the Arabic text lacks mathematical symbolism, and it
appears to be based on a later Greek commentary—perhaps that of Hypatia (c.
370–415)—that diluted Diophantus’s exposition. We now know that the numbering of the
Greek books must be modified: Arithmetica thus consists of Books I to III in Greek, Books IV to
VII in Arabic, and, presumably, Books VIII to X in Greek (the former Greek Books IV to VI).
Further renumbering is unlikely; it is fairly certain that the Byzantines only knew the six books
they transmitted and the Arabs no more than Books I to VII in the commented version.
The contents of the three missing books of the Arithmetica can be surmised from the
introduction, where, after saying that the reduction of a problem should “if possible” conclude
with a binomial equation, Diophantus adds that he will “later on” treat the case of a trinomial
equation—a promise not fulfilled in the extant part. Although he had limited algebraic tools at
his disposal, Diophantus managed to solve a great variety of problems, and
the Arithmetica inspired Arabic mathematicians such as al-Karajī (c. 980–1030) to apply his
methods. The most famous extension of Diophantus’s work was by Pierre de
Fermat (1601–65), the founder of modern number theory. In the margins of his copy
of Arithmetica, Fermat wrote various remarks, proposing new solutions, corrections, and
generalizations of Diophantus’s methods as well as some conjectures such as Fermat’s last
theorem, which occupied mathematicians for generations to come. Indeterminate equations
restricted to integral solutions have come to be known, though inappropriately,
as Diophantine equations.
Source: https://www.britannica.com/biography/Diophantus.

68
 Introduction

From the previous lesson, you have explored linear Diophantine equations and
applied Euclidian algorithm and reverse the process to find only one solution to
these equations. In this lesson, we will study how to find all the integer solutions for
linear Diophantine equations.

Objectives

1. Solve linear Diophantine equations; and

2. Find all integer solutions for a given linear Diophantine equation.

Suggested Learning Time 1 hour and 30 minutes to 2 hours

Let’s Try Answering This!

Describe all integer solutions to the following equation.

105x + 121y = 1

69
Let’s check whether your answers are correct.
105x + 121y = 1 Let a = 105, b = 121
121= 1 x 105 + 16 b = 1 x a + 16
105 = 6 x 16 + 9 16 = b - a
16 = 1 x 9 + 7 a = 6 (b - a) + 9
9=1x7+2 9 = a - 6b + 6a = 7a - 6b
7 = 2 x 3 + 1 (gcd) b - a = 1 x (7a - 6b) + 7

3=1x3+0 b - a - 7a + 6b = 7
- 8a + 7b = 7
7a - 6b = 1 x (- 8a + 7b) + 2
7a - 6b + 8a - 7b = 2
15a - 13b = 2
- 8a + 7b = 15a - 13b(3) + 1
1 = - 8a + 7b - 45a + 39b
- 53a + 46b = 1
Thus, x = - 53 and y = 46

Check:
- 53a + 46b = 1
- 53 (105) + 46 (121) = -5565 + 5566 = 1

All solutions are given by :

( -53 + 121k, 46 - 105k) where k is any integer

Were you able to solve the equation? Great job!

If not, don’t worry it is just an assessment of your background knowledge about the
lesson.
Now, let us move on to learning the lesson.

Let’s Study This!

The whole discussion on this lesson was obtained from Silverman (2012).
We know that the equation

ax + by = gcd (a,b)

always has a solution in integers x and y. But we can also investigate the
question of how many solutions a given equation has, and how to describe all
the solutions.

Let’s start with the case that a and b are relatively prime, that means,
gcd (a,b) = 1 and suppose that (x1, y1) is a solution to the equation

ax + by = 1

70
 We can create additional solutions by adding a multiple of b from x1 and
subtracting the same multiple of a onto y1. In other words, for any integer k we
obtain a new solution (x1 + kb, y1 - ka ). We can check that this is indeed a solution
by computing

a(x1 + kb) + b (y1 - ka) = ax1 + akb + by1 - bka = ax1 + by1 = 1

So, for example, if we start with the solution (-1, 2) to 5x + 3y = 1, we obtain

new solutions (x1 + kb, y1 - ka) = (-1 + 3k, 2 - 5k). Note that the integer k is
allowed to be positive, negative, or zero. Putting in particular values of k gives the
solutions.
(2, -3), (5, -8), (8, -13), (11, -18)…
… ( -13, 22) , (-10, 17), (-7, 12), (-4, 7), (-1, 2),

Still looking at the case that gcd (a,b) = 1, we can show that this procedure gives
all possible solutions. Suppose that we are given two solutions (x1, y1) and (x2, y2) to
the equation ax + by = 1. In other words,

ax1 + by1 = 1 and ax2 + by2 = 1

We are going to multiply the first equation by y2, multiply the second equation
by y1 and subtract.
y2 (ax1 + by1 = 1) = ax1y2 + by1y2 = y2

y1 (ax2 + by2 = 1) = ax2y1 + by2y1 = y1

This will eliminate b and, after a little bit of algebra, we are left with

ax1y2 - ax2y1 = y2 - y1

Similarly, if we multiply the first equation by x2, multiply the second equation by
x1, and subtract, we find that

bx2y1 - bx1y2 = x2 - x1

So if we let k = x2y1 - x1y2, then we find that

x2 = x1 + kb and y2 = y1 - ka

This means that the second solution (x2, y2) is obtained from the first solution
(x1,y1) by adding a multiple of b onto x1 and subtracting the same multiple of a from
y1 . So every solution to ax + by = 1 can be obtained from the initial solution (x1, y1)
by substituting different values of k into (x1 + kb, y1 - ka).
What happens if gcd (a,b) > 1 ? To make the formulas look a little bit simpler,
we will let g = gcd (a,b). We know from the Euclidian algorithm method that there is
at least one solution (x1, y1) to the equation

71
 ax + by = g

But g divides both a and b, so (x1, y1) is a solution to the simpler equation

a b
x  y 1
g g

Now our earlier work applies, so we know that every other solution can be
obtained by substituting values for k in the formula

b a
x1  k  , y1  k 
g g

This completes our description of the solutions to the equation ax + by = g, as

summarized in the following theorem.
Theorem 6.1 (Linear Equation Theorem). Let a and b be nonzero integers, and
let g = gcd (a,b). The equation
ax + by = g

always has a solution (x1, y1) in integers, and this solution can be found by the
Euclidian algorithm method described previously. Then every solution to the
equation can be obtained by substituting integers k into the formula

b a
x1  k  , y1  k 
g g

For example, we saw that the equation

60 x  22 y  gcd(60,22)  2

has the solution x = 4, y = 11. (Recall how we solved linear Diophantine equations in
the previous lesson.) Then our Linear Equation Theorem says that every solution is
obtained from the formula
b a
x1  k  , y1  k 
g g

That is, (- 4 + 11k, 11 - 30k) with k any integer

In particular, if we want a solution with x positive, then we can take k = 1, which

gives the smallest such solution (x, y) = (7, -19).

72
 Let’s Apply This!

Determine all solutions in the integers of the following Diophantine equations.

(a) 56x + 72y = 40

(b) 24x + 138y = 18

c) 221x + 35y = 11

73
 Let’s Test Your Understanding!

Determine all solutions in the integers of the following Diophantine equations.

(a) 18x + 5y = 48

(b) 54x + 21y = 906

c) 123x + 360y = 99

74
 Useful References:

Burton, D.M. (2007). Elementary number theory (6th ed.) The McGraw-Hill
Companies, Inc.

Clark, W.E. (2003) Elementary number theory (1st ed.) Department of Mathematics.
University of South Florida.

Sesiano, J. (2019, June 6). Diophantus. Encyclopædia Britannica.

https://www.britannica.com/biography/Diophantus.

Rosen, K.H. (1986). Elementary number theory and its applications. Addison -
Wesley Publishing Company.

Silverman, J.H. (2012). A friendly introduction to elementary number theory (4th ed.)
Pearson Education, Inc.

75