Number Theory: Diophantine Equations

Number Theory studies the properties of integers, in particular, positive integers -- a.k.a. the natural numbers as referred to by the ancient Greeks. As a student of Abstract or Modern Algebra I find it interesting that most proofs in that field are based on number theoretic arguments. It is customary to apply the term Diophantine equation to any equation in one or more unknowns which is to be solved in the integers.

The mathematician Diophantus lived in Alexandria sometime around 250 A.D.. Diophantus's reputation rests on his great work Arithmetica which may be described as the earliest treatise on algebra. It is in this work that we find the first systematic use of mathematical notation.

THEOREM: The linear Diophantine equation ax + by = c has a solution if and only if d divides c; written: d|c, where d = the greatest common divisor of a and b; written: (gcd)(a,b). If x0, y0 is any particular solution of this equation, then all other solutions are given by

x = x0 + (b/d)t,
y = y0 - (a/d)t

for varying integers t.

EXAMPLE

56x + 72 y = 40

*******************

THEOREM: Given integers a and b, not both zero, there exist integers x and y such that

gcd(a,b) = ax + by.

The proof of this reveals that the greatest common divisor of a and b may be described as the smallest integer of the form ax + by.

For our example, to find a particular solution in x and y we first want to find the greatest common divisor of 56 and 72. And, in order to find the greatest common divisor of two numbers, we employ the Euclidean Algorithm which itself employs repeated applications of the Division Algorithm.

The first step is: a = q1b + r1, where q1 is an integer and r1 is a remainder.

By the Euclidean Algorithm, we have:

72 = 1 × 56 + 16
56 = 3 × 16 + 8
16 = 2 × 8 + 0

The last nonzero remainder of the Division Algorithm is equal to gcd (a,b).

Accordingly: 8 = gcd (56, 72)

This is based on:

LEMMA: if a = bq + r, then gcd (a,b) = gcd (b,r).

*******************

From the theorem:
The Diophantine equation ax + by = c admits a solution if and only if d|c, where d = gcd (a, b)
[Proof of this statement lies below.]

Therefore, the last remainder of our example, our greatest common divisor -- 8 -- must divide c = 40 for there to be a solution.

Backtracking the Euclidean Algorithm, we start with the next to last of the displayed equations above and eliminate remainders.

There are only three, so we have:

8 = 56 - 3 × 16
= 56 - 3(72 - 56)
= 56 - 3(72) + 3(56)
= 4(56) - 3(72)

40 = 5 * 8 = 20(56) - 15(72)

Therefore,
x = 20 + 9t --- [x = x0 + (b/d)t]
y = -15 - 7t --- [y = y0 - (a/d)t]
(for varying integers t)

************************

Proof: There are integers r and s for which a = dr and b = ds. If a solution of ax + by = c exists, so that [ax0 + by0 = c] for suitable x0 and y0, then

c = ax0 + by0 = drx0 + dsy0 = d( rx0 + sy0),

which simply says that d|c.

Conversely, assume that d|c, say c = dt. Integers x0 and y0 can be found satisfying

d = ax0 + by0.

When this relation is multiplied by t, we get

c = dt = (ax0 + by0)t = a(tx0) + b(ty0).

Hence, the Diophantine equation ax + by = c has x = tx0 and y = ty0 as a particular solution.

************************