Euclidean Algorithm, more than two variables

Printable View

March 7th 2013, 04:57 AM
sirellwood

Euclidean Algorithm, more than two variables

Hi all,

Ok, so im more than comfortable with the Euclidean Algorithm when I have only two numbers so it is of the form

an + bm = r

But now i have the equation 225a + 360b + 432c + 480d = 3, and i need to find the integers a,b,c and d to satisfy this.

So i know the gcd is 3, and I realise how you can get to that by finding the gcd, x of two of the numbers and then finding the gcd of x and one of the other numbers and so forth. But now I am stuck wondering how I go about using the method of back substitution to find the integers a,b,c and d?

Thanks!
March 8th 2013, 04:42 AM
BobP

Re: Euclidean Algorithm, more than two variables

We can get a solution with three applications of the Euclidean Algorithm, I don't know if it possible to do any better.

To begin with we may as well divide throughout by 3,
75a + 120b +144c + 160d = 1.

Next, group as
3(25a + 48c) + 40(3b + 4d) = 1.
There are probably other groupings available, you just have to see that the three pairs of numbers (3,40), (25,48), (3,4) are each relativley prime.

Now rewrite as 3A + 40B = 1 and use the EA to find values for A and B.
A = -13, B = 1 are solutions (and there will be an infinity of others).

That gets you
25a + 48c = -13, and 3b + 4d = 1.

Solve these to get (again with an infinity of other possibles) a = 299, b = -1, c = -156 and d = 1.
March 8th 2013, 10:12 AM
Zeno

Re: Euclidean Algorithm, more than two variables

I have a question. Will this always work?

The original equation given was 225a + 360b + 432c + 480d = 3

Can I swap the 3 out for any arbitrary whole number n and still be guaranteed to always get a solution using this method?

Like so: 225a + 360b + 432c + 480d = n And then just chose any n by whim (assume a whole number choice).

Or was this equation "rigged" in some way beforehand?
March 8th 2013, 10:42 AM
Jame

Re: Euclidean Algorithm, more than two variables

n must be the gcd or a multiple of the gcd
March 9th 2013, 12:27 AM
ILikeSerena

Re: Euclidean Algorithm, more than two variables

Quote:

Originally Posted by sirellwood

Hi all,

Ok, so im more than comfortable with the Euclidean Algorithm when I have only two numbers so it is of the form

an + bm = r

But now i have the equation 225a + 360b + 432c + 480d = 3, and i need to find the integers a,b,c and d to satisfy this.

So i know the gcd is 3, and I realise how you can get to that by finding the gcd, x of two of the numbers and then finding the gcd of x and one of the other numbers and so forth. But now I am stuck wondering how I go about using the method of back substitution to find the integers a,b,c and d?

Thanks!

Hi sirellwood! :)

You can extend the Euclidean Algorithm for this.
The algorithm just keeps track of a set of equations that are true, reducing the remainder step by step, until it can be reduced no further.

Like BobP I'll reduce your equation first to 75a + 120b +144c + 160d = 1
Then the initial set of equations is:

. $\begin{matrix}a & b & c & d \end{matrix}$

$\begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 75 \\ 120 \\ 144 \\ 160 \end{bmatrix} = \begin{bmatrix} 75 \\ 120 \\ 144 \\ 160 \end{bmatrix}$

Select the equation with the lowest remainder, which is 75.
Multiply that equation by a number and add it to each of the other equations.
Select the number to multiply with such that the absolute value of the new remainder becomes as low as possible.
Like this:

$\begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 75 \\ 120 \\ 144 \\ 160 \end{bmatrix} = \begin{bmatrix} 75 \\ 120 \\ 144 \\ 160 \end{bmatrix} \begin{matrix} * \\ -2 \\ -2 \\ -2 \end{bmatrix}$

The result is:

$\begin{bmatrix}1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ -2 & 0 & 1 & 0 \\ -2 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 75 \\ 120 \\ 144 \\ 160 \end{bmatrix} = \begin{bmatrix} 75 \\ -30 \\ -6 \\ 10 \end{bmatrix}$

Two more iterations, and you'll get:

$\begin{bmatrix}-29&0&14&1 \\ 8&1&-5&0 \\ 16&0&-5&-3 \\ -6&0&2&1 \end{bmatrix} \begin{bmatrix} 75 \\ 120 \\ 144 \\ 160 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ -2 \end{bmatrix}$

In other words, you get the solution:

$75 \cdot -29 + 120 \cdot 0 + 144 \cdot 14 + 160 \cdot 1 = 1$

You can construct other solutions by adding any of the other equations, multiplied by any number, to it.
March 9th 2013, 04:55 PM
Zeno

Re: Euclidean Algorithm, more than two variables

ILikeSerena,

Can you explain the two iterations you left out?

I'm just learning matrix multiplication and I don't understand how you created that final matrix.

Thanks.
March 9th 2013, 05:09 PM
ILikeSerena

Re: Euclidean Algorithm, more than two variables

Quote:

Originally Posted by Zeno

ILikeSerena,

Can you explain the two iterations you left out?

I'm just learning matrix multiplication and I don't understand how you created that final matrix.

Thanks.

Oh, I've already thrown those iterations away.

Let's see if I can walk you through.
Note that the matrix is just a short hand notation for a set of 4 equations.

$\begin{bmatrix}1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ -2 & 0 & 1 & 0 \\ -2 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 75 \\ 120 \\ 144 \\ 160 \end{bmatrix} = \begin{bmatrix} 75 \\ -30 \\ -6 \\ 10 \end{bmatrix}$

In this set of equations, the lowest remainder is -6.
To get the remainder 75 as low as possible, you need to add -6 a total of 12 times.
Since we're really talking about a set of equations, we need to multiply the third row by 12 and add the result to row one.
What do you think the first row will become?
March 9th 2013, 07:25 PM
Zeno

Re: Euclidean Algorithm, more than two variables

Quote:

Originally Posted by ILikeSerena

Oh, I've already thrown those iterations away.

Let's see if I can walk you through.
Note that the matrix is just a short hand notation for a set of 4 equations.

$\begin{bmatrix}1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ -2 & 0 & 1 & 0 \\ -2 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 75 \\ 120 \\ 144 \\ 160 \end{bmatrix} = \begin{bmatrix} 75 \\ -30 \\ -6 \\ 10 \end{bmatrix}$

In this set of equations, the lowest remainder is -6.
To get the remainder 75 as low as possible, you need to add -6 a total of 12 times.
Since we're really talking about a set of equations, we need to multiply the third row by 12 and add the result to row one.
What do you think the first row will become?

I have no clue what I'm doing here with matrix multiplication. I actually took a course in linear algebra about 30 years ago. And I did pretty good in that course, but apparently I forget everything.

Ok, let me take a stab at this.

row three appears to be:

$\begin{bmatrix}-2 & 0 & 1 & 0 \end{bmatrix}$

So if I multiple that by 12 I should get:

$\begin{bmatrix}-24 & 0 & 12 & 0 \end{bmatrix}$

And then adding that to row one I should get:

$\begin{bmatrix}-23 & 0 & 12 & 0 \\ -2 & 1 & 0 & 0 \\ -2 & 0 & 1 & 0 \\ -2 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 75 \\ 120 \\ 144 \\ 160 \end{bmatrix} = \begin{bmatrix} ? \\ ? \\ ? \\ ? \end{bmatrix}$

I forget how to multiply matrices:

I'll take a stab at it:

$\begin{bmatrix}-23 & 0 & 12 & 0 \\ -2 & 1 & 0 & 0 \\ -2 & 0 & 1 & 0 \\ -2 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 75 \\ 120 \\ 144 \\ 160 \end{bmatrix} = \begin{bmatrix} 3 \\ -30 \\ -6 \\ 10 \end{bmatrix}$

Is that right?

What do I do next then? Add 3 times row 4 to row 2, and 2 times row three to row four?

$\begin{bmatrix}-23 & 0 & 12 & 0 \\ -8 & 1 & 0 & 3 \\ -2 & 0 & 1 & 0 \\ -6 & 0 & 2 & 1 \end{bmatrix} \begin{bmatrix} 75 \\ 120 \\ 144 \\ 160 \end{bmatrix} = \begin{bmatrix} 3 \\ 0 \\ -6 \\ -2 \end{bmatrix}$

Now what?

Start again with the -2? Add 1 times row 4 to row 1, and -3 times row 4 to row 3?

Let's see if that works:

$\begin{bmatrix}-29 & 0 & 14 & 1 \\ -8 & 1 & 0 & 3 \\ 16 & 0 & -5 & -3 \\ -6 & 0 & 2 & 1 \end{bmatrix} \begin{bmatrix} 75 \\ 120 \\ 144 \\ 160 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ -2 \end{bmatrix}$

I have no clue what I just did, but my final matrix appears to be different from the final matrix you got. But the coeffients for a, b, c, and d came out the same.

I'll have to mess around with this some more when I'm not so tired.

How do I know that I'm done?

What's that -2 doing still dangling there?
March 10th 2013, 12:02 AM
ILikeSerena

Re: Euclidean Algorithm, more than two variables

It seems I don't have to explain anything.
You've got it down! :D

The reason your result is different is because you took different steps than I did.
But that doesn't matter as long as you did not make mistakes.
To verify if you made mistakes, you can check each row.
For instance row 2 is [-8 1 0 3].
Multiply with respectively [75 120 144 160], add them all up and verify that the result is the same as the remainder, which is [ 0 ].

The key result is the row that has the remainder 1, which is the first row.
It gives you a solution.
Once you have that you can stop.
Or else you can stop when you can't get the remainder any lower.
However, there is more than one solution.
Each row with remainder zero can be added to the row with the solution.
Doing so will still yield 1 as remainder and get you another solution.

That -2 is still dangling because you didn't clean it up yet.
It's not really necessary, but if you want you can add row 1 twice to row 4, and then it will be zero as well.

The full set of solutions is the following:

Let lcm be the least common multiple of your coefficients in your original equation.
That is, lcm = lcm(75,120,144,160).

$a = -29 + \frac{lcm}{75} n_1$
$b = 0 + \frac{lcm}{120} n_2$
$c = 14 + \frac{lcm}{144} n_3$
$d = 1 - \frac{lcm}{160} n_1 - \frac{lcm}{160} n_2 - \frac{lcm}{160} n_3$

where $n_1, n_2, n_3$ are arbitrary integers.
If you substitute these solutions in the original equation, you should see that the equation is satisfied for choices for $n_1, n_2, n_3$ .
March 10th 2013, 10:56 AM
Zeno

Re: Euclidean Algorithm, more than two variables

Quote:

Originally Posted by ILikeSerena

That -2 is still dangling because you didn't clean it up yet.
It's not really necessary, but if you want you can add row 1 twice to row 4, and then it will be zero as well.

I was actually thinking that last night but was too tired to continue. So it should be possible then to always clean a problem like this up to all zeros save for the first 1.

Another question:

Is this matrix algebra basically doing the same thing as Euclid's Algorithm?

Quote:

Originally Posted by ILikeSerena

The full set of solutions is the following:

Let lcm be the least common multiple of your coefficients in your original equation.
That is, lcm = lcm(75,120,144,160).

$a = -29 + \frac{lcm}{75} n_1$
$b = 0 + \frac{lcm}{120} n_2$
$c = 14 + \frac{lcm}{144} n_3$
$d = 1 - \frac{lcm}{160} n_1 - \frac{lcm}{160} n_2 - \frac{lcm}{160} n_3$

where $n_1, n_2, n_3$ are arbitrary integers.
If you substitute these solutions in the original equation, you should see that the equation is satisfied for choices for $n_1, n_2, n_3$ .

That's nice additional information in case you ever need to come up with specific values for a, b, c, or, d in a particular situation.

~~~~~

This wasn't even my problem, but I enjoyed going through it. Ironically I just happen to be studying both Euclid's Elements right now, and I also have a need to get back into Linear Algebra again, so this problem served two purposes for me. (Rock)
March 10th 2013, 11:08 AM
ILikeSerena

Re: Euclidean Algorithm, more than two variables

Quote:

Originally Posted by Zeno

Another question:

Is this matrix algebra basically doing the same thing as Euclid's Algorithm?

This is Euclid's algorithm, although normally it is applied to 2 variables and 2 equations.
The matrix notation is circumstantial and only intended to organize what we're doing.
I wouldn't even really call it matrix algebra.
The notation is useful to keep track of systems of equations without writing everything out.
March 11th 2013, 07:41 AM
sirellwood

Re: Euclidean Algorithm, more than two variables

Ok, so looking at peoples replies, I see that no one is leaving it in the form 225a + 360b + 432c + 480d = 3,

I left it like this and worked backwards through the algorithm and produced answers

a = 3
b = -28
c = -196
d = 196

Plugging these back into 225a + 360b + 432c + 480d = 3, it satisfies the equation. But I am wondering if this isnt acceptable, seeing as no one suggested to do it this way?

thanks
March 11th 2013, 11:08 AM
ILikeSerena

Re: Euclidean Algorithm, more than two variables

Quote:

Originally Posted by sirellwood

Ok, so looking at peoples replies, I see that no one is leaving it in the form 225a + 360b + 432c + 480d = 3,

I left it like this and worked backwards through the algorithm and produced answers

a = 3
b = -28
c = -196
d = 196

Plugging these back into 225a + 360b + 432c + 480d = 3, it satisfies the equation. But I am wondering if this isnt acceptable, seeing as no one suggested to do it this way?

thanks

The solutions are the same whether we divide by 3 or not.
Dividing by 3 makes the numbers smaller, which is easier to deal with.
The algorithm also works with this original equation, although you won't get to a remainder of 1, but you'll find a remainder of 3.