Diophantine Again

In my last post I introduced you to Linear Diophantine Equations.(Let us call them LDE for short)
We couldn’t help Alice but there were lessons learnt. (For example we shouldn’t be dreaming while spending money and later find to our dismay that some mystical equation fails to get our balances right  )
Yet again I will like to emphasise that there can be lots of different ways to approach the same problem and you don’t need to follow exactly same steps to arrive at a solution.
Steps I outlined are very broad in nature.
You are free to follow your own course with basics in mind.
You must have already noticed that we depend a lot on the Bezout equation.

That is for two integers a and b we can have

ax+by = GCD(a,b)


I cannot overemphasise how important this equation is.
If you think a bit you will realise that this equation immediately gives us a way to relate two strangers in the world of integers a and b.
a and b can be anything and yet we find to our delight that they are related.
And as you might expect mathematicians have a special name for this kind of relation.
We say that GCD(a,b) can be expressed as linear combination of a and b.
This is just another way of saying that three numbers GCD(a,b),a and b are related.

To put it more formally we say that three entities say A,B,G are LINEARLY DEPENDENT if we can write a equation relating them as
xA+yB+zG=0
such that x ,y,z are not all zero. So if you think a bit you will immediately notice that Bezout equation accomplishes exactly the same thing. So if you plug in a for A , b for b and GCD(a,b) for G we can say with full confidence that these are linearly related for we know for sure we can find values for x and y such that they are not zero.
Note that g is -1.

Actually g=-1 or x and y are some values determined by Euclid’s Algorithm really doesn’t make any difference as long as they are not equal to zero all at a same time.
You can also extend this idea to n entities A,B,C,D,E….. instead of just three of them.

Now supposing we cannot find a solution and only way to relate A,B,G through a equation is such that x=y=z=0.Then we say A,B,G are LINEARLY INDEPENDENT. Fortunately we are not going to deal with such estranged entities, not for now at least.

So let us revisit the same old LDE and this time in a more systematic way.
Say we want to solve
4P+2E=18
Since GCD(4,2) = 2
And since 2|18 we know there is a solution.

We can start with Bezout equation for 4 and 2
4x+2y =2
We try to find x and y
One solution is x=1 and y=-1 you can find this by trial and error.
So we write
4(1)+2(-1)=2
Multiply by 9 and get

4(9)+2(-9)=18

So P=9 and E=-9 is a solution.

We try to find all possible solutions.
I will tell you how to write the solution immediately then furnish a proof.

Say we have equation ax+by =c

And supposing we found one solution. x0 ,y0 .In this case we found (9,-9)
Then all values for x and y can be found as following.

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

t is free running parameter. For each value of t we obatin a new solutuion.
t can be any integer negative , positive or 0.Thus we can write with equal justification .

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

Which means whether you put t with minus sign in first equation or last doesn’t matter as long they appear with opposite signs in the two equations. This is because t can be negative integer as well.

Now what is multiplied by t is b or a divided by GCD(a,b)
Notice that it is b when we are finding x. So if we are finding x we take coefficient of y.
And when we are finding y we take coefficient of x.So we exchange coefficients for x and y.

Say we want a general solution of P and E
We just found P=9 and E=-9

So we can immediately write general solution for P we can write
We already know GCD(4,2) = 2

So we can write
P=(9)+t(2/2) or P=9 + t 1



This 2 is GCD(4,2)


2 is coefficient of E that’s why it appears here in expression for P
We exchange the coefficients for P and E.

Similarly for for E we can write

E = (-9) –t (4/2) or E = (-9) - 2t



This 2 is GCD(4,2)




This 4 is coefficient of P that’s why it appears in
expression for E. We exchange coefficients.




So we have P=9+t
And E=-9-2t
As I already mentioned that if we write
P=9-t
and E =-9 +2t this set will also be correct .Sign of t doesn’t matter as log as it is opposite in these two equations. And we can proceed with any one of them without giving a second thought.

So let us retain the first.
P=9+t
E=-9-2t for now and proceed.
Out of infinite possible solutions for all values of t we know that Pencils and Erasers can’t be negative so we can write.
P>0 and E >0
If you notice if we give negative values for t , E tends to get a more positive value.
Note that if we give t=-5 then we get E=1 and P=4
If we give t=-6 then E= 3 and P=3
if t=-7 then E=5 and P=2
if t=-8 then E=7 and P=1
if t=-9 then E=9 and P=-1 and here we have to stop as erasers are becoming negative so we have four solutions.
We could have written all this a bit more compactly
We already know P > 0 so P=9+t > 0 or t > -9
And E>0 gives -9-2t > 0 or -9 > 2t or -9/2 > t or -4.5> t
But since t can be integer only so -4.5 > t means -5 >t

So we get
P=9+t
E=-9-2t where -9 < t < -5 All this looks very neat in three lines.


I will show you yet another example then we will be done for LDEs.
This time we chose a LDE which looks like it means business.
3456x+246y=234
Here we first find GCD(3456,246)
So we start with Euclid’s Algorithm

246| 3456 |14
- 246
---------------------
996
-984
-----------------------
12|246 |20
-24
-----------------------------
xx6 |12 |2
-12
------------------------------
xx

So 6 is the GCD
We immediately check whether 6 divides 234 it does so we have a solution.
Now we have to determine a solution for 3456x+246y=234
We start by writing steps in Euclid’s Algo.
3456=246*14+12 => 12 = 3456 -246 *14 …..Equation 1
246=12*20+6 => 6= 246 -12*20 … Equation 2
12=6*2 /* Not needed */

Substitute 12 in equation 2 by expression for 12 in equation 1
So 6= 246 – (3456 -246*14)*20
6= 246- 3456*20 +246*280
6= 246*281 -3456*20 This is it.
Multiply the whole thing by 39
6*39 =246*(281*39)-3456*(20*39)
234=246 *(10959)-3456*(780)
So one solution is 10959,780
We can now write the complete solution.
x= 10959 + t *(3456/6) so x=10959 +t * 576
y=780 - t*(246/6) so y=780-t*41 where t is any integer.
Depending upon whether x,y stand for pencils and erasers of forgetful Alice or Number of coins in my pocket you can enforce conditions like x>0 and y>0 and get a subset of above solution..(Yes here you end up with so many coins in your pocket. A pound has 100 pence and here each pence counts. Even one pence is valued. Wonder what happened to our own paisa)


Now I think if you see a LDE you can immediately write the solution just by looking at it. Let us hope we have better luck with Alice next time.