Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-09-13 12:31:52

mortage762
Member
Registered: 2007-05-04
Posts: 6

GCD question

I was wondering - how would one find a solution in integers to the following equation?:

54321x + 9876y = gcd(54321, 9876)

Thanks in advance!

Offline

#2 2007-09-13 13:30:12

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: GCD question

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

#3 2007-09-13 13:40:57

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

Re: GCD question

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

#4 2007-09-13 13:51:29

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

Re: GCD question

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

#5 2007-09-13 15:57:59

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: GCD question

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

Board footer

Powered by FluxBB