Find complete set of integer solutions

Printable View

January 28th 2011, 07:11 PM
mathematic

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.
January 28th 2011, 07:37 PM
dwsmith

Quote:

Originally Posted by mathematic

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.
January 28th 2011, 08:23 PM
mathematic

So fo x, i would solve:
216,630+1997t>0
216,630>-1997t
216,630/-1997<t?
February 7th 2011, 07:07 PM
mathematic

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
February 7th 2011, 09:08 PM
dwsmith

Quote:

Originally Posted by mathematic

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.