Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By TheEmptySet
  • 1 Post By MaxJasper

Math Help - Solving equation with two unknown integers

  1. #1
    Member
    Joined
    Nov 2011
    Posts
    87

    Red face Solving equation with two unknown integers

    Hi everyone!

    I have my own comfortable way of solving equations with two unknowns like:

    5s + 42t = 1

    What I do when I solve this equation, is that I first think: ok, the absolute value of s must be bigger than the absolute value of t in order to get an answer as close to 1 as possible. Than I try t = 1, t = 2... and test with the appropriate s in order to get an answer as close to 1 as possible. The problem is that my method becomes extremely long for big numbers such as

    123 456 s + 654 321 t = 3

    Does anyone perhaps know some easy to use, good method which would solve these kind of equations efficiently?

    Thank you all so much for reading this!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78

    Re: Solving equation with two unknown integers

    Quote Originally Posted by Nora314 View Post
    Hi everyone!

    I have my own comfortable way of solving equations with two unknowns like:

    5s + 42t = 1

    What I do when I solve this equation, is that I first think: ok, the absolute value of s must be bigger than the absolute value of t in order to get an answer as close to 1 as possible. Than I try t = 1, t = 2... and test with the appropriate s in order to get an answer as close to 1 as possible. The problem is that my method becomes extremely long for big numbers such as

    123 456 s + 654 321 t = 3

    Does anyone perhaps know some easy to use, good method which would solve these kind of equations efficiently?

    Thank you all so much for reading this!
    Yes. This can be solve using the Euclidean algorithm. You can also look at this Bézout's identity - Wikipedia, the free encyclopedia

    42=5(8)+2
    5 = 2(2)+1

    Now we can back substitue to get

    1= 5-2(2)= 5-2(42-5(8))=5(17)+42(-2)

    Note we now have the equation

    \\ 5(17)+42(-2)=1 \\ 5s+42t=1

    So s=17 and t=-2
    Thanks from Nora314
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member MaxJasper's Avatar
    Joined
    Aug 2012
    From
    Canada
    Posts
    482
    Thanks
    54

    Lightbulb Re: Solving equation with two unknown integers

    More s, t:

    \{s,t\}=\{-67,8\},\{-25,3\},\{17,-2\},\{59,-7\},\text{...}
    Thanks from Nora314
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2011
    Posts
    87

    Re: Solving equation with two unknown integers

    Thank you so much for posting an answer!

    I took a look at the Wikipedia page you linked to and it makes more sense now. Though, I still have some trouble completely understanding this. I know how to use the Euclidean algorithm so the first part of your post makes sense to me. Though, when you start substituting I get a little bit lost. Like when you write 1 = 5 - 2(2), I understand that you found the number 2 by using the Euclidean algorithm, but I am not sure why you chose to substitute exactly that number in that way.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78

    Re: Solving equation with two unknown integers

    Quote Originally Posted by Nora314 View Post
    Thank you so much for posting an answer!

    I took a look at the Wikipedia page you linked to and it makes more sense now. Though, I still have some trouble completely understanding this. I know how to use the Euclidean algorithm so the first part of your post makes sense to me. Though, when you start substituting I get a little bit lost. Like when you write 1 = 5 - 2(2), I understand that you found the number 2 by using the Euclidean algorithm, but I am not sure why you chose to substitute exactly that number in that way.
    What I was doing was find the GCD of the two numbers. This is sometimes called the reverse Euclidean alogorithm, or extended Euclidean algorithm.
    We can always frind the GCD of two numbers this way. There are a few example on this wiki page.

    Extended Euclidean algorithm - Wikipedia, the free encyclopedia

    This is why the equation only has solutions if

    \gcd(a,b)|c
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,750
    Thanks
    650

    Re: Solving equation with two unknown integers

    Hello, Nora314!

    I have my own way, too.


    \text{Solve the Diophantine equation: }\:5s + 42t \:=\: 1

    Solve for the variable with the smaller coefficient.

    . . s \:=\:\frac{\text{-}42t + 1}{5} \quad\Rightarrow\quad s \:=\:\text{-}8t + \frac{1-2t}{5} .[1]


    Since s is an integer, . 1-2t must be a multiple of 5.

    . . Hence: . 1-2t \:=\:5a\:\text{ for some integer }a.

    Then: . t \:=\:\frac{\text{-}5a + 1}{2} \quad\Rightarrow\quad t \:=\:\text{-}2a + \frac{1-a}{2} .[2]

    We see that a must be odd: . a \:=\:2k-1


    Substitute into [2]: . t \:=\:\text{-}2(2k-1) + \frac{1-(2k-1)}{2}
    . . which simplifies to: . t \:=\:\text{-}5k-2


    Substitute into [1]: . s \:=\:\text{-}8(\text{-}5k-2) + \frac{1-2(\text{-}5k-2)}{5}
    . . which simplifies to: . s \:=\:42k+17


    Therefore: . \begin{Bmatrix} s &=& 42k+17 \\ t &=& \text{-}5k -2 \end{Bmatrix}\;\text{ for any integer }k.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Maple - solving the unknown t
    Posted in the Math Software Forum
    Replies: 4
    Last Post: April 9th 2012, 11:24 AM
  2. Solving for unknown varilable
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 5th 2011, 11:08 AM
  3. Solving for unknown
    Posted in the Algebra Forum
    Replies: 2
    Last Post: June 9th 2010, 08:02 AM
  4. Need help solving an unknown
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 10th 2010, 07:23 AM
  5. Replies: 3
    Last Post: November 7th 2009, 02:21 PM

Search Tags


/mathhelpforum @mathhelpforum