1. Diophantine equation

I'm trying to write a program that solves linear Diophantine equations. I'm having difficulties finding information regarding the subject and how, in detail, it is solved. I've googled for days now and found calculators that have other equations without a description of what they mean so I can understand what's being done.

Is anyone able to provide me information as to how someone would solve any linear Diophantine equation in the forms: $ax+by=c$ or $ax+by+cz=d$?

I have three sample cases and the program I write seems to only be solvable to one of them. The problem I'm having is signs, and I haven't even gotten to the 3 term Diophantine yet.

I've been mostly using: 87x-64y=3 and 6x+9y=30
I had a calculator that worked perfectly for 87x-64y=3 or 87x+-64y=3but as soon as I try 6x+9y=30, nothing makes sense. I suspect I'm having a signing(+/-) problem, but maybe if I further understood a linear Diophantine equation and it's general process of solution, I could resolve that issue. Maybe it's my poor algebra skills that need work, I don't know.

2. Re: Diophantine equation

Have you considered the value of first determining if there IS a solution? A little number theory would get you there.

4. Re: Diophantine equation

Originally Posted by TKHunny
Have you considered the value of first determining if there IS a solution? A little number theory would get you there.
This is easily solved by whether or not C Modulo GCD(A, B) = 0. There are also a few other pitfalls that determine whether or not there is a solution. If it gets beyond that and there are no positive solutions available in a finite number set, then I will pseudo no-solution the equation. I will read up on number theory though, thanks for the suggestion.

Originally Posted by ymar
Try reading Euclidean algorithm - Wikipedia, the free encyclopedia
I think I have the Elucidian algorithm down. My problem is when I get beyond the Extended Elucidian algorithm, putting the quotients into a table and getting the Bezout's identity, that I start to have troubles. I think creating the identity is of somewhat trouble to me, although I may have solved the identity issue, I am not getting beyond that. However, I have been messing with my identity code and broke it and have to start it from scratch since I can't figure out what I broke. It's only a couple lines anyway.

I don't know if you know Python coding but this is what I have for the Elucidian and Extended Elucidian algorithms.
Code:
######################
###Elucid Algorithm###
######################
def ElucidAlgorithm(a, b):
global aTable#if abs(a) > abs(b) 0 else 1
global bTable#if abs(b) > abs(a) 0 else 1
print '###Elucid Algorithm###'
print '######################'
print 'Elucid Algorithm: ' + str(a) + ', ' + str(b)
#dividend = divisor * quotient + modulo
quotients = []
divisors = []
if aTable:
dividend = a
divisor = b
else:
dividend = b
divisor = a
divisors.append(divisor)
quotient = int(dividend / divisor)
quotients.append(quotient)
modulo = dividend % divisor
print 'Elucid Algorithm: ' + str(dividend) + ' = ' + str(divisor) + ' * ' + str(quotient) + ' + ' + str(modulo)
while modulo != 0:
dividend = divisor
divisor = modulo
divisors.append(divisor)
quotient = int(dividend / divisor)
quotients.append(quotient)
modulo = dividend % divisor
print 'Elucid Algorithm: ' + str(dividend) + ' = ' + str(divisor) + ' * ' + str(quotient) + ' + ' + str(modulo)
if divisor * quotient == dividend:
print 'Elucid Algorithm: Return (' + str(a) + ', ' + str(b) + ') ' + str(divisor)
return [divisor, quotients, divisors]
else:
print 'Elucid Algorithm: Return no solutions'
return 0
###############################
###Extended Elucid Algorithm###
###############################
def ExtendedElucidAlgorithm(a, b):
global aTable
global bTable
print '###Extended Elucid Algorithm###'
print '###############################'
gcdQuosDivs = ElucidAlgorithm(a, b)
if gcdQuosDivs != 0:
##################
###TABLE METHOD###
##################
print '###Extended Elucid Algorithm: TABLE  METHOD###'
print '##############################################'
#populate table
print 'Extended Elucid Algorithm: Populate table'
table = [[0,1], [1,0]]
for quotient in gcdQuosDivs[1]:
table[aTable].append(quotient * table[aTable][len(table[aTable]) - 1] + table[aTable][len(table[aTable]) - 2])
table[bTable].append(quotient * table[bTable][len(table[bTable]) - 1] + table[bTable][len(table[bTable]) - 2])
row0 = 'a('+str(a)+'): '
row1 = 'b('+str(b)+'): '
for x in range(0, len(table[aTable])):
row0 = row0 + str(table[aTable][x]) + ' '
row1 = row1 + str(table[bTable][x]) + ' '
print 'Extended Elucid Algorithm: ' + row0
print 'Extended Elucid Algorithm: ' + row1
print 'Extended Elucid Algorithm: Return table'
return [gcdQuosDivs, table]
else:
print 'Extended Elucid Algorithm: Return no solutions'
return 0

5. Re: Diophantine equation

Unfortunately, I don't understand Python, so I won't help you with the code. I can tell you however how to solve your equation. Maybe this will clear some things up. We have

6x+9y=30

By the EA, we can find that NWD(6,9)=3. We check whether 3 divides 30. It does, so our equation has solutions. We divide both sides of the equation by NWD(3,6)=3 in order to deal with smaller numbers. It could as well be done later. Anyway, we get

2x+3y=10

We have an equation of the form ax+by=c such that NWD(a,b)=1. We know that the equation

ax+by=1

has solutions in this case. Let's solve this equation.

2x+3y=1

2(x+y)+y=1

Let's substitute s=x+y. We obtain

2s+y=1

that is

y=-2s+1

where s is an arbitrary integer. We have

x+(1-2s)=s

so

x=3s-1

Hence, our equation has the following solution

(3s-1,-2s+1), s \in Z.

For s=0, we get (-1,1), which is -- not by coincidence -- what we would have gotten from the extended EA. It is also not a coincidence that the slopes are equal 3 and -2, that is b and -a. These always work.

We have solved

2x+3y=1

Now we want to solve

2x+3y=10

To do that, all we have to do is multpily our solution by 10.