Linear Diophantine Equations

We start with Alice.(If you like you may think of her from Alice in Wonderland)

Supposing Alice went to market and bought a few pencils and a few erasers. Alice paid Rs 18 in all. Later she distributed all Pencils and Erasers she bought among her friends in Wonderland. Later back from Wonderland,very much in reality her mother demanded what did she do with 18 rupees she had. Now Alice had no clue how many pencils she bought and how many erasers, but she knew pencils cost 4 and erasers cost 2 and all 18 rupees she had were spent on them.

So for Alice and all such forgetful, dreamy people let us see how number theory can come to aid.

Let us assume she bought P pencils and E erasers.

Then we must have 4P+2E=18



Where P and E are integers .Problem is that we have just one equation and two unknowns P and E. However we have one more information that is P and E are integers.



If you look at form of equation you will immediately recall the Bezout equation which says

For two numbers a,b

We can write xa+yb =GCD(a,b)

And we have 4,2 here instead of a and b.

And P,E instead of x,y

So how do we go about it.



First of all note what we can write for 4 and 2



It is this x4+y2=GCD(4,2)=2

Or x4+y2=2

So if 2 doesn't divide 18 we cannot have a solution.

This is because in the end

x4+y2 =2 and P4+E2=18 are identical equations and we have just tweaked x and y by multiplying them with something to get P and E.

So P/x=E/y=18/2



If you recall linear equations in two variable for x,y

a1x+b1y=c1

and a2x+b2y=c2



if a1/a2=b1/b2 then solution is possible only if



a1/a2=b1/b2=c1/c2= k



And if a1/a2=b1/b2 not equal to c1/c2 then there is no solution.

What this means is that second equation is just first equation multiplied by some constant k.

So k(a1x+b1y=c1) gives a2x+b2y=c2.

And in terms of equation it means you are not going to get an INDEPENDENT equation by just multiplying the first with a constant.





So much for equations let us come to rescue Alice.

We write

x4+y2 =2

and P4+E2=18



Step 1 divide P4+E2=18 by GCD(4,2) i,e by 2



or P2+E=9



Now we obtain another equation P2+E1=9

we have another equation in terms of 2 and 1.

2 and 1 have gcd =1

So it is possible to write for some s,t s2+t1 =1 (bezout equation for 2 and 1)

By trial and error we get s=-1 and t=3.You can use Euclid's Algo as well.



So (-1)2 +(3)1=1



Multiply whole thing by 9.

And get (-9)2+(27)1=9 analogous to P2+E1=9



Again multiply by 2

(-9)4+(27)2=18 analogous to P4+E2=18



And this is the same equation we have been searching for.

and we can have on comparing coefficients P=-9 and E=27

But something is wrong Alice cannot buy negative number of pencils.

So what do we do now.

It turns out there is a neat trick in mathematics to handle this kind of problems.



Step 2



Supposing we take the equation

4-(2)2=0



We can add this equation any number of times to (-9)4+(27)2=18

without changing anything. Because adding zeros doesn't change anything.

Note the negative coefficient of 4. It is -9

So if we add 4 ten times we can make it positive.

So 10 * (4- (2)2)=0 gives

(10)4-(20)2=0



Adding this to original equation (-9)4+(27)2=18 gives

4+(7)2=18

or (1)4+(7)2=18

So finally we can conclude



Alice bought 1 pencil and 7 erasers.



But wait I found that adding 4-2(2)=0 doesn't change anything. So I can add any multiple of this to main equation and obtain another new solution.

In fact there are infinite number of solutions. But the fact that Alice must have bought positive number of erasers and pencils might save the day .Let us see

Supposing we add 11 times the 4-2(2)=0 to (-9)4+(27)2=18 we get (2)4+(5)2=18

And 13 times we get (3)4+(3)2=18

And 14 times we get (4)4+(1)2=18

Any further we will have pencils as negative.

So Alice is undone She might have bought . 1,7 or 2,5 or 3,3 or 4,1

pencils and erasers respectively.

So sorry Alice we cannot help you.



This class of equations

ax+by =c

is called Linear Diophantine Equation.



I just showed you how to solve one.