You are not logged in.
#1 2012-10-20 02:28:00
- Johnathon bresly
- Guest
Equation
Is there a method for solving the equation ax+by=c where a,b,c are constants and x,y are integers
#2 2012-10-20 02:37:57
- zetafunc.
- Guest
Re: Equation
If a, b and c are integers then that looks like a linear diophantine equation, and we know certain properties of that equation. For example, if c = gcd(a,b), then there are an infinite number of solutions. You can use the extended Euclidean algorithm to find those. And if we're considering gcd(a,b), then if c isn't a multiple of gcd(a,b), then that equation has no solutions.
#3 2012-10-20 02:56:19
- Johnathon bresly
- Guest
Re: Equation
Could you explain it further(i don't know the Euclidean algorithm)
#4 2012-10-20 11:31:44
- bobbym
- Administrator
Online
Re: Equation
Hi;
If the gcd(a,b) does not divide c then there are no solutions.
If gcd(a,b)= d and d does divide c then there are an infinite number of solutions.
The simplest way is to get a particular solution by trial and error. This is feasible because of the simplicity of the equations.
Once you have a particular solution x0 and y0 you can get all of them by these parametric equations.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#6 2012-10-20 12:11:15
- bobbym
- Administrator
Online
Re: Equation
Hi;
Trial and error is not exactly guessing it is just the simplest without learning more math.
If you do want more, read this first it will give an example of the extended GCD algorithm.
http://mathworld.wolfram.com/DiophantineEquation.html
Come back then with your questions.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#7 2012-10-20 18:43:19
- Johnathon bresly
- Guest
Re: Equation
I am sorry but i use mobile phone to go to internet and that link is not visible to me so it'd be better if you explain it here,and i have learned the euclidean algorithm now,(not the extended one)
#8 2012-10-20 20:12:55
- bobbym
- Administrator
Online
Re: Equation
Hi Johnathon bresly;
Here is a method to do this;
This is best understood using an example:
First find the gcd(1124,84), which equals 4.
Here are the steps.
Now we back substitute starting with the second to last step.
So then a solution of
is
x = 8 and y = -107
There is a much better way to do this using a backward recurrence but you would need to go to another page to see it.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#9 2012-10-21 01:36:18
- Johnathon bresly
- Guest
Re: Equation
This back substitution is a little complex,is there any rule for which number to substitute in the steps?
#10 2012-10-21 03:44:02
- Johnathon bresly
- Guest
Re: Equation
Oh,I understand it now,but what is it with the other solution method.
#11 2012-10-21 07:18:26
- bobbym
- Administrator
Online
Re: Equation
Hi;
The other method is somewhat simpler but requires a knowledge of recurrence or difference equations. Are you up to that?
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#12 2012-10-21 11:51:32
- Johnathon bresly
- Guest
Re: Equation
I will try my best to understand those methods,so please post them.
#13 2012-10-21 12:07:32
- bobbym
- Administrator
Online
Re: Equation
Hi;
Okay, I will need some time to post it. Or are you able to download a pdf file if I give you a link?
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#15 2012-10-21 12:31:51
- bobbym
- Administrator
Online
Re: Equation
Hi;
Let's do an example:
To solve this you form the following table:
The first two rows are just the GCD algorithm applied to 74 and 54.
The last row is generated by the following trick. See the 1 and the 0 that are boxed off they are always given. To get the 2 you take the number before it (second boxed number (1)) and multiply it by the top row number that is in the same column. So that is (1)(2), now you add the number 2 before it ( second boxed number ) (1)(2) +1 = 3.
To get the next number you take number before it and times it by the top row, same column and add the number before that.
(2)(1)+1 = 3.
Next is (3)(2)+2 = 8.
Last is (8)(1)+3 = 11. Now the whole table is filled up and ready for the final stage.
Cross multiply the first 2 numbers in the second and third row.
So x =-8 and y = 11 is a solution.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#16 2012-10-21 17:15:10
- Johnathon bresly
- Guest
Re: Equation
I have quite understand it,30 minutes ago I searched in wikihow and found a similar way.
#17 2012-10-21 17:23:21
- bobbym
- Administrator
Online
Re: Equation
Hi Johnathon bresly;
You posted before I was done. There is more up there now.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.