A Diophantine equation is "*an algebraic equation in one or more unknown with integer coefficients for which integer solutions are sought*". This according to the text '* What Is Mathematics?*' (p. 50) Further such an equation may have: " no solutions, a finite number of solutions, or an infinite number." The basic template for this type of equation is: ax + by = c.

Here, a, b and c denote integers and the equation
needs to be solved for x and y, and ideally these solutions are integers, not
fractions. At this point, we have to cut to the Euclidean algorithm and
how it's used. A general theorem may be stated thus: If a is any integer,
and b is any integer greater than zero, then we can always find an integer q
such that:

a = b*q + r

where r is an integer satisfying the inequality:
0 < r < b

A general task is to find the “*greatest common
divisor*” (gcd) of a and b, called d(a,b). If d = (a,b)then positive or
negative integers k and m can always be found such that: d = ka + mb

This proceeds by successive divisions with remainders.
As an example, consider the Euclidean algorithm for finding (a,b) = (61, 24).
Here gcd or greatest common divisor is 1 and we find:

61 = 2*24 + 13

24 = 1*13 + 11

13 = 1*11 + 2

11 = 5*2 + 1

2 = 2*1 + 0

From the 1st equation we have: 13 = 61 - 2*24

From the end of the second result we get:

11 = 24 – 13 = 24 - 61 - 2*24 = -61 + 3*24

From the third:

2 = 13 – 11 = (61 – 2*24) – (-61 + 3*24) = 2*61 –
5*24

From the fourth:

1 = 11 – 5*2 = (-61 + 3*24) –
5(2*61 – 5*24) = -11.61 + 28*2

Apart from these operations, we can also use the Euclidean
algorithm to compute continued fractions. For example, consider 169/70 and seek the continued
fraction development:

169/70 = 2 + 29/70 = 2 + 1/70/29

70/29 = 2 + 12/29 = 2 + 1/ (29/12)

29/12 = 2 + 5/18 = 2 + 1/ (12/5)

12/5 = 2 + 2/5 = 2 + 1/(5/2)

And: 5/2 = 2 ½ = 2 + ½

Thus, as shown in the diagram below, 169/70
is developed with the result = 2.414

Let's now see how the preceding operations can be used to solve a Diophantine equation. In particular, we want to solve: 7x + 11y = 13 We proceed by working with 7 and 11, respectively, using the Euclidean algorithm.

Thus: 11 = 1*7 + 4 and 7 = 1*4 + 3

We see remainder 4 for the first, so use the algorithm again, so: 4 = 1*3 + 1

Then we can write: (7, 11) = 1

Meanwhile, the remainder of 1 (after working on remainder 4) is dealt with, so:

1 = 4 - 3 = 4 - (7 - 4) = 2*4 - 7 = 2 (11 - 7) - 7 = 2*11 - 3*7

Therefore: 7*(-3) + 11(2) = 1 and 7*(-39) + 11(26) = 13

From the last equation
we see that x = -39 and y = 26.

All other solutions can be expressed in terms of x and y -values with a
remainder r (integer), so that: x = -39 + 11r and y = 26 -
7r

For example, let r = 1, then x = (-39) + 11 = - 28 is also a
solution. Similarly, let r = 1 and y = 26 -7 (1) = 26 - 7 = 19 is also a solution.

In summary then, the linear Diophantine equation of form ax +
by = c has a solution in integers if and only if c is a multiple of (a, b). In
this case, a particular solution may be found using the Euclidean
algorithm.

__Suggested Problems:__

1)
Solve the
Diophantine equation: 3x - 4y = 29

(Give at least one extra solution to the one immediately proposed)

2)Solve the Diophantine equation: 11x + 12 y = 58

(Give at least one extra solution to the one immediately proposed)

## No comments:

Post a Comment