Part 1

This may seem as a big topic, and it is by far the most complex topic of all, because it simply has too many possibilities to consider. One of the famous equations of all time is this:

, where are unknowns and is the constant.

We are then asked to solve for .

This may seem as a very hard problem to solve, but with enough mathematical knowledge, this can be solved easily. (Solutions are at the end of the whole post–not this post)

Important thing to note:

- Only
**integer**solutions are allowed for diophantine equations. This narrows the solution range by a lot,and is worth taking note of. - A linear diophantine equation generally takes the form of

Before learning anything, we will first introduce a mathematical algorithm, namely the Euclidean Algorithm (Also known as the Euclid’s Algorithm). It is an algorithm commonly used in finding the **greatest common divisor**(GCD) of two integers and .

***Below is the proof for the Euclid’s Algorithm, you may ignore this and continue reading from ##.**

To make things easier for us to see, we assume with .

Therefore, we are safe to say that , where . Then, find a number which divides both and , so that and , with be real constants). Then, also divides since

.

Similarly, find a number which divides and (so that and ). Then divides since

.

Therefore, every common divisor of and is a common divisor of and . Proceeding recursively, we obtain:

with

with

with

with

.

.

Eventually, for some , and the algorithm terminates. Therefore, the GCD of and is

.

**##**

If you do not understand the proof, an example of an application of the Euclid’s algorithm is at below:

Let and

Another example:

Let and

After you know this algorithm, you are one step closer in solving linear diophantine equations.

Cheers,

etzhky =)

Part 2

Once you know how to apply the Euclid’s Algorithm, it will be more easier to solve linear diophantine equations involving 2 variables.

Let us see the general form of a linear diophantine equation:

Does every equation of this form has a solution where ?

Obviously, the answer is no. I will list some counter-examples:

;

For the first equation, the L.H.S. is even, where the R.H.S. is odd, which creates a contradiction — there is no solution for . Similarly, for the second equation, the L.H.S. is a multiple of three, where the R.H.S. is not, also creates a contradiction which implies that there is also no solution for .

This will lead us to a general statement (This is were Euclid’s Algorithm comes in handy) — if , then has no solution. However, when , has infinite solutions. We will see why is the case now. (You can skip this proof and continue reading from ##)

** Proof

Suppose that we have a solution to the equation . Then, the other solutions will be:

and , where .

Indeed, after we substitute the values inside the original equation,

.

Thus we can deduce that the original equation has infinitely many integers solutions.

Also, let be , thus and , then one solution may be found by determining such that from the equation , where .

#### ##

For the sake of convenience, we will say that all other solutions are given by:

and , where , with and .

Take note that represents , and . Take this as a formula to solve Diophantine equations. Let me use a simple example to make use of this formula.

**Example 1**

Solve for integer :

**Solution 1**

First, we check that whether this equation has integer solutions using the Euclid’s Algorithm:

.

Thus , and since , this equation does have integer solutions. To actually find the solutions we need to reverse the steps in Euclid’s Algorithm (I don’t think further explanation is needed because it is relatively easy to understand):

.

So, we take and ( and ).

Therefore, applying the formula, all the solutions are

, .

where .

I shall now use a new example to clarify any doubts.

**Example 2**

Find all positive integer solutions to the equation .

**Solution 2**

Note that the question imposed limitations to the solution — it must be positive. So, after getting the general solutions, we must conform to the limitations of the question.

Using the Euclid’s Algorithm,

.

Thus, , and since , this equation does have integer solutions. Next, reverse the steps of the Euclid’s Algorithm.

Thus, we take and .

Thereafter, applying the formula we get the general solution of the equation.

,

——-(1)

———(2)

Since , we get the simultaneous inequality:

Therefore the range of values for is , which implies that .

Substitute both values of into both equations (1), (2), we get:

.

Thus the equation has two pair of solutions, and .

For the solution to the equation

, where are unknowns and is a non-negative constant,

it has infinite solutions for , but only trivial solutions for . It is the famous Fermat’s Last Theorem. You can find more about it on the web.

Cheers,

etzhky