Results 1 to 5 of 5

Math Help - Diophantine equation

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    2

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,110
    Thanks
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: Diophantine equation

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2011
    Posts
    2

    Re: Diophantine equation

    Quote 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.

    Quote 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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Diophantine equation
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: July 23rd 2011, 09:51 PM
  2. Diophantine equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 30th 2010, 12:44 PM
  3. Diophantine Equation? Or something?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 1st 2010, 03:10 PM
  4. diophantine equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 8th 2008, 04:37 PM
  5. A diophantine equation
    Posted in the Number Theory Forum
    Replies: 28
    Last Post: June 23rd 2006, 04:19 AM

Search Tags


/mathhelpforum @mathhelpforum