You are not logged in.
Pages: 1
I was wondering - how would one find a solution in integers to the following equation?:
54321x + 9876y = gcd(54321, 9876)
Thanks in advance!
Offline
http://www-math.cudenver.edu/~wcherowi/courses/m5410/exeucalg.html
There is a neat trick you can use to calculate it very quickly. I will do this example with gcd(20, 32).
First, divide the smaller into the larger. Here, 20 goes in to 32 1 time with a remainder of 12. Now each step we will divide the remainder into the previous divisor.
Step 1: 20 goes into 32: 1 time with remainder 12
Step 2: 12 goes into 20: 1 time with remainder 8
Step 3: 8 goes into 12: 1 time with remainder 4
Step 4: 4 goes into 8: 2 times with no remainder.
Here, the divisor of the last step is our GCD, in this case, it is 4. Now we take all of the results from the division, make them negative, and reverse the order. What we end up with is this chart:
-1 -1 -1
Add a 0 and a 1 to the bottom left:
-1 -1 -1
0 1
Now the pattern is to do the first column times the box to the bottom left of it, then add on the box to the left of that.
First step: -1 * 1 + 0 = -1. So our new chart becomes:
-1 -1 -1
0 1 -1
Second step: -1 * -1 + 1 = 2 So our chart becomes:
-1 -1 -1
0 1 -1 2
Third step: -1 * 2 + -1 = -3
-1 -1 -1
0 1 -1 2 -3
Now we take our last two numbers, and we use them in the equation:
20x + 32y = gcd(20, 32)
Here, we see that:
20(-3) + 32(2) = 4 = gcd(20, 32)
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
No can do.
x=2 and y = 11, off by 6
x=4 and y = 22, off by 12
x = 6 and y = 33, off by 18
x = 8 and y = 44, off by 24
Sorry, I can't do it, maybe you can't.
igloo myrtilles fourmis
Offline
Woops, Ricky was right, I was wrong.
(54321)(-1645) + (9876)(9048) = 3
54321
+
9876 * -5
=
4941, so + 4941 * -1
=
4935, so + 4935 * -1
to the 4941 and get 6.
Then +6 * -822
to the 4935 to get 3.
Then 6-3 is 3, and 3 = 3 so we are done.
Then do as Ricky said.
-822 -1 -1 -5
0 1 -822 823 -1645 9048
because you do this:
A B C D
0 1 1A+0 1AB+1 C(1AB+1)+1A gets longer here.
call or or or
it E BE+1 CF + E DG + F
,call it F ,call it G
Use G and DG+F for your answers..., the -1645 and the 9048.
Thanks Ricky!!! That's awesome!!
Last edited by John E. Franklin (2007-09-13 14:02:21)
igloo myrtilles fourmis
Offline
John, there is a theorem which states:
For any integers n and m, there exists integers x and y such that nx + ym = gcd(n, m). Furthermore, if nx + ym = d, then gcd(n, m) divides d.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
Pages: 1