Linear Diophantine Equations

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:

$x^n+y^n=z^n$ , where $x,y,z$ are unknowns and $n$ is the constant.

We are then asked to solve for $x,y,z$ .

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 $ax+by=c$

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 $a$ and $b$ .

*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 $a,b > 0$ with $a>b$ .

Therefore, we are safe to say that $a=q_0b+r_0$ , where $0 leq r_0 < b$ . Then, find a number $u$ which divides both $a$ and $b$ , so that $a = su$ and $b = tu$ , with $s,t$ be real constants). Then, $u$ also divides $r$ since

$r = a - bq=su-qtu=(s-qt)u$ .

Similarly, find a number $v$ which divides $b$ and $r$ (so that $b=s'v$ and $r=t'v$ ). Then $v$ divides $a$ since

$a = bq+r=s'vq+t'v=(s'q+t')v$ .

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

$a = q_0b+r_0$ with $0 \leq r_0 < b$

$b = q_1r_0+r_1$ with $0 \leq r_1< r_0$

$r_0 = q_2r_1+r_2$ with $0 \leq r_2< r_1$

$r_1 = q_3r_2+r_3$ with $0 \leq r_3< r_2$

Eventually, $r_n = 0$ for some $n$ , and the algorithm terminates. Therefore, the GCD of $a$ and $b$ is

$gcd(r_{n-1},r_n) = gcd (r_{n-1}, 0) = r_{n-1}$ .

##

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

Let $a=2322$ and $b=654$

$2322 = 654 \cdot 3 + 360$
$654 = 360 \cdot 1 + 294$
$360=294\cdot1+66$
$294=66\cdot4+30$
$66=30\cdot2+6$
$30=6\cdot5$
$\therefore gcd(2322,654) = 6$

Another example:

Let $a=5678$ and $b=1234$

$5678 = 1234 \cdot 4 + 742$
$1234 = 742 \cdot 1 + 492$
$742=492\cdot1+250$
$492=250\cdot1+242$
$250=242\cdot1+8$
$242=8\cdot30+2$
$8=2\cdot4$
$\therefore gcd(5678,1234) = 2$

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:

$ax+by=c$

Does every equation of this form has a solution $(x,y)$ where $a,x,b,y,c \in Z$ ?

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

$2x+4y=1$ ; $3x+6y=2$

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 $(x,y)$ . 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 $(x,y)$ .

This will lead us to a general statement (This is were Euclid’s Algorithm comes in handy) — if $gcd(a,b) \nmid c$ , then $(x,y)$ has no solution. However, when $gcd(a,b)|c$ , $(x,y)$ 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 $(x_0,y_0)$ to the equation $ax+by=c$ . Then, the other solutions will be:

$x=x_0+b_1t$ and $y=y_0-a_1t$ , where $\forall t \in Z$ .

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

$ax+by=ax_0+ab_1t+by_0-ba_1t=(ax_0+by_0)+(da_1b_1t-db_1a_1t)=c+0=c$ .

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

Also, let $gcd(a,b)$ be $d$ , thus $a=a_1d$ and $b=b_1d$ , then one solution may be found by determining $u,v$ such that $d = ua + vb$ from the equation $ax+by=c$ , where $u,v \in Z$ .

##

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

$\displaystyle{x=x_0+t\cdot\frac{b}{d}}$ and $\displaystyle{y=y_0-t\cdot\frac{a}{d}}$ , where $\forall t \in Z$ , with $\displaystyle{x_0 = u\cdot\frac{c}{d}}$ and $\displaystyle{y_0=v\cdot\frac{c}{d}}$ .

Take note that $d$ represents $gcd(a,b)$ , and $d=ua+vb$ . 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 $(x,y)$ :

$77x+42y=35$

Solution 1

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

$77 = 42 \cdot 1+35$
$42 = 35 \cdot 1+7$
$35 = 7 \cdot 5+0$ .

Thus $gcd(77,42) = 7$ , and since $7|35$ , 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):

$7=42-35 \cdot 1=42-(77-42 \cdot 1)=(-1) \cdot 77+ 2\cdot 42$ .

So, we take $u=-1$ and $v=2$ ( $a=77$ and $b=42$ ).

Therefore, applying the formula, all the solutions are

$\displaystyle{x_0= -1 \cdot \frac{35}{7} = -5}$ , $\displaystyle{y_0=2\cdot\frac{35}{7}=10}$ .
$\displaystyle{x=x_0+t\cdot\frac{42}{7}=-5+6t}$
$\displaystyle{y=y_0+t\cdot\frac{77}{7}=10-11t}$

where $t \in Z$ .

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

Example 2

Find all positive integer solutions to the equation $12x+5y=125$ .

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,

$12 = 5 \cdot 2 + 2$
$5=2\cdot 2 +1$
$2=1\cdot 2 + 0$ .

Thus, $gcd(12,5)=1$ , and since $1|125$ , this equation does have integer solutions. Next, reverse the steps of the Euclid’s Algorithm.

$1=5-2\cdot 2=5-2\cdot(12-5\cdot 2) = (-2)\cdot 12 + 5\cdot 5$

Thus, we take $u=-2$ and $v=5$ .

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

$\displaystyle{x_0=-2\cdot\frac{125}{1}=-250}$ , $\displaystyle{y_0=5\cdot\frac{125}{1}=625}$
$\displaystyle{x=-250+t\cdot\frac{5}{1}=5t-250}$ ——-(1)
$\displaystyle{y=625-t\cdot\frac{12}{1}=625-12t}$ ———(2)

Since $x,y>0$ , we get the simultaneous inequality:

$5t-250>0$
$625-12t>0$

$5t>250$
$12t<625$

$t>50$
$t<52.1$

Therefore the range of values for $t$ is $50<t<52.1$ , which implies that $t=51,52$ .

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

$(x,y)=(5\cdot 51-250,625-12\cdot 51)=(5,13)$
$(x,y)=(5\cdot 52-250,625-12\cdot 52)=(10,1)$ .

Thus the equation has two pair of solutions, $(5,13)$ and $(10,1)$ .

For the solution to the equation

$x^n+y^n=z^n$ , where $x,y,z$ are unknowns and $n$ is a non-negative constant,

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

Cheers,
etzhky