Results 1 to 5 of 5

Math Help - Find complete set of integer solutions

  1. #1
    Member
    Joined
    Jan 2011
    Posts
    79

    Find complete set of integer solutions

    Find the complete set of integer solutions in x and y to
    821x + 1997y = 24047:
    Determine all solutions with x > 0 and y > 0.




    I started by finding the GCD(821, 1997)=1
    Then I went backwards using the Euclidean algorithm and found 1=821(90)-1997(37).
    So we have a particular solution xo=90, y0=-37.
    Our particular solution is x0=24047*90=216630 and y0=24047*-37=-889,739.
    then I have:
    x=216,630+1997t and y=-889,739-821t.
    Now it's the final part of determining all solutions with x>0 and y>0 that's getting me.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by mathematic View Post
    Find the complete set of integer solutions in x and y to
    821x + 1997y = 24047:
    Determine all solutions with x > 0 and y > 0.

    I started by finding the GCD(821, 1997)=1
    Then I went backwards using the Euclidean algorithm and found 1=821(90)-1997(37).
    So we have a particular solution xo=90, y0=-37.
    Our particular solution is x0=24047*90=216630 and y0=24047*-37=-889,739.
    then I have:
    x=216,630+1997t and y=-889,739-821t.
    Now it's the final part of determining all solutions with x>0 and y>0 that's getting me.
    ax+by=c \ \ \ d=\text{GCD}(a,b)

    \displaystyle x=x_0+\left(\frac{b}{d}\right)t, \ \ \ y=y_0-\left(\frac{a}{d}\right)t

    Restrict t as necessary.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jan 2011
    Posts
    79
    So fo x, i would solve:
    216,630+1997t>0
    216,630>-1997t
    216,630/-1997<t?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jan 2011
    Posts
    79
    I'm a little confused on how you got those t values. I know it should be a pretty simple calculation.
    Here's what I have done:
    821x + 1997y = 24047
    Use Division Algorithm to find GCD.
    1997=821(2)+355
    821=355(2)+111
    355=111(3)+22
    111=22(5)+1
    22=1(22)+0
    Then (821, 1997)=1 and 1|24047. So the equation is solvable.
    1=111-22(5)
    1=111-[355-111(3)]5
    1=111(16)-355(5)
    1=[821-355(2)]16-355(5)
    1=821(16)-355(37)
    1=821(16)-[1997-821(2)]37
    1=821(90)-1997(37)
    So 821x+1997y has a solution (90, -37) and thus 821x+1997y=24047 has a particular solution (2164230, -889739).
    The general solution is given by:
    x=2164230+1997t
    y=-889739-821t
    We have x>0.
    Then 2164230+1997t>0
    1997t>-2164230
    t>-1083.74
    We have y>0.
    Then -889739-821t>0
    -821t>889739
    t<1083.72
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by mathematic View Post
    I'm a little confused on how you got those t values. I know it should be a pretty simple calculation.
    Here's what I have done:
    821x + 1997y = 24047
    Use Division Algorithm to find GCD.
    1997=821(2)+355
    821=355(2)+111
    355=111(3)+22
    111=22(5)+1
    22=1(22)+0
    Then (821, 1997)=1 and 1|24047. So the equation is solvable.
    1=111-22(5)
    1=111-[355-111(3)]5
    1=111(16)-355(5)
    1=[821-355(2)]16-355(5)
    1=821(16)-355(37)
    1=821(16)-[1997-821(2)]37
    1=821(90)-1997(37)
    So 821x+1997y has a solution (90, -37) and thus 821x+1997y=24047 has a particular solution (2164230, -889739).
    The general solution is given by:
    x=2164230+1997t
    y=-889739-821t
    We have x>0.
    Then 2164230+1997t>0
    1997t>-2164230
    t>-1083.74
    We have y>0.
    Then -889739-821t>0
    -821t>889739
    t<1083.72
    First, lets check if it is solvable.

    Does d|c?

    (821,1997)=1

    so 1|c.

    1=821(90)-1997(37)\Rightarrow 24047=24047(821)(90)-1997(37)(24047)\Rightarrow 24047=821(2164230)-1997(889739)

    x_0=2164230 \ \ \ y_0=889739

    x=2164230+1997t \ \ \ \ y=-889739-821t

    t=-1084

    That is the only value of t that will work.
    Last edited by dwsmith; February 7th 2011 at 09:47 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Find the number of integer solutions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 24th 2011, 05:52 PM
  2. Find integer solutions to 1/x + 1/y = 1/14
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 16th 2011, 12:16 PM
  3. Find all integer solutions to an equation
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: September 8th 2010, 01:05 PM
  4. Replies: 11
    Last Post: March 29th 2010, 11:34 AM
  5. Replies: 4
    Last Post: July 24th 2008, 02:02 AM

Search Tags


/mathhelpforum @mathhelpforum