Linear Diophantine Equation Solution

- way back in time when reviewing for licensure board examination, one problem that I had to deal with was Linear Diophantine Equation Solution
- it is solving one equation, 2 unknowns
- sharing it to you



An Example of Linear Diophantine Equation Solution

A Diophantine equation is an equation in which only integer solutions are allowed.

The mathematician Diophantus of Alexandria (200-284 AD) gave a
general solution for when problems of this type are solvable. Of
course he was only interested in integer solutions, so when we say a
problem like this is solvable, we mean that there exist integers x and
y such that ax + by = c.

Condition: c is divisible by Greastest Common Denominator (gcd) of a and b.
GCD of a and b can be determined by Euclidean algorithm.

Greater than one solution:

x = x' + (b/d)*t
y = y' - (a/d)*t

where d = gcd(a,b)
t = is an arbitrary integer.



Sample 1:

Find the integer a and b in the equation 1027a + 712b = 1.


Solution:

step 1:  Find GCD by downward calculation.

1027 = 712 x 1 + 315  equation 6
712 = 315 x 2 + 82  equation 5

315 =  82 x 3 + 69  equation 4
82 =  69 x 1 + 13  equation 3
69 =  13 x 5 + 4        equation 2
13 =   4 x 3 + 1  equation 1
4 =   1 x 4 + 0     GCD

4 = Greatest Common Denominator of 1027 and 712.


step 2:  Upward calculation.  Starting from equation 1.

1 =  13 - (4x3)
=  13 - (69 - 13x5) x 3       from equation 2
=  13 x 16 - 69 x 3
=  (82 - 69) x 16 - 69 x 3      from equation 3
=  82 x 16 - 69 x 19
=  82 x 16 - (315 - 82 x 3) x 19    from equation 4
=  82 x 73 - 315 x 19 
=  (712 - 315 x 2) x 73 - 315 x 19    from equation 5
=  712 x 73 - 315 x 165
=  712 x 73 - (1027 - 712) x 165    from equation 6
=  712 x 238 - 1027 x 165

Answer:  a = 165, b =238