Results 1 to 13 of 13
Like Tree2Thanks
  • 2 Post By BobP

Math Help - Euclidean Algorithm, more than two variables

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1

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

  2. #2
    Super Member
    Joined
    Jun 2009
    Posts
    658
    Thanks
    131

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

  3. #3
    Junior Member
    Joined
    May 2011
    Posts
    29
    Thanks
    1

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

  4. #4
    Member
    Joined
    Feb 2011
    Posts
    83
    Thanks
    2

    Re: Euclidean Algorithm, more than two variables

    n must be the gcd or a multiple of the gcd
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Euclidean Algorithm, more than two variables

    Quote Originally Posted by sirellwood View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    May 2011
    Posts
    29
    Thanks
    1

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

  7. #7
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Euclidean Algorithm, more than two variables

    Quote Originally Posted by Zeno View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    May 2011
    Posts
    29
    Thanks
    1

    Re: Euclidean Algorithm, more than two variables

    Quote Originally Posted by ILikeSerena View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Euclidean Algorithm, more than two variables

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

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

  10. #10
    Junior Member
    Joined
    May 2011
    Posts
    29
    Thanks
    1

    Re: Euclidean Algorithm, more than two variables

    Quote Originally Posted by ILikeSerena View Post
    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 View Post
    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.
    Last edited by Zeno; March 10th 2013 at 11:03 AM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Euclidean Algorithm, more than two variables

    Quote Originally Posted by Zeno View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1

    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
    Last edited by sirellwood; March 11th 2013 at 07:58 AM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Euclidean Algorithm, more than two variables

    Quote Originally Posted by sirellwood View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 5th 2011, 05:59 AM
  2. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 19th 2010, 11:13 AM
  3. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 08:28 AM
  4. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 10th 2008, 08:17 PM
  5. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 13th 2007, 07:20 AM

Search Tags


/mathhelpforum @mathhelpforum