# Math Help - elem.num.theo - diophantine equations w/word problems

1. ## elem.num.theo - diophantine equations w/word problems

OK: long story short, restrictions are positive integers - the book gives us 63x+7=23y
so I start:
63 = (-23)(-2) + 17
-23 = 17(-1) + (-6)
17 = (-6)(-2) + 5
-6 = (5)(-1) + (-1)
5 = (-1)(-5) + 0
so gcd(63,-23)=-1

does this work? I mean with the whole negative thing? because I continue on like that and eventually get:
x = 28 + 23t
y = 77 + 63t
where t>0
then I get, t>(-28/23) and t>(-77/63)
and I'm stuck. Because it has to be positive - and it has to be an integer

therefore - i think it has to do with the negatives - how would one go about them?

2. Originally Posted by cassiopeia1289
OK: long story short, restrictions are positive integers - the book gives us 63x+7=23y
so I start:
63 = (-23)(-2) + 17
-23 = 17(-1) + (-6)
17 = (-6)(-2) + 5
-6 = (5)(-1) + (-1)
5 = (-1)(-5) + 0
so gcd(63,-23)=-1

does this work? I mean with the whole negative thing? because I continue on like that and eventually get:
x = 28 + 23t
y = 77 + 63t
where t>0
then I get, t>(-28/23) and t>(-77/63)
and I'm stuck. Because it has to be positive - and it has to be an integer

therefore - i think it has to do with the negatives - how would one go about them?
the gcd cannot be negative.

anyway, it seems to me that your solutions for x and y (which, since you did so well on the last problem, i assume are right--perhaps with a factor of a minus sign if you indeed took the gcd to be -1) will be positive as long as $t \ge -1$, where t is an integer

3. Originally Posted by cassiopeia1289
OK: long story short, restrictions are positive integers - the book gives us 63x+7=23y
does this work? I mean with the whole negative thing? because I continue on like that and eventually get:
x = 28 + 23t
y = 77 + 63t
where t>0
then I get, t>(-28/23) and t>(-77/63)
and I'm stuck. Because it has to be positive - and it has to be an integer

therefore - i think it has to do with the negatives - how would one go about them?
Note that

x = 28 + 23(-1) = 5
y = 77 + 63(-1) = 14

is a solution in positive integers.

4. ok, but if the gcd can't be negative - how do I even approach this problem to begin with??

5. Originally Posted by cassiopeia1289
ok, but if the gcd can't be negative - how do I even approach this problem to begin with??
the same way you did the last one. you want to find the solutions to 7 = (-63)x + 23y

furthermore, note that $\text{gcd}(a,b) = \text{gcd}(|a|,|b|)$

so gcd(63, -23) = gcd(-63, 23) = gcd(-63, -23) = gcd(63,23) = +1

6. ah - haha, ok,

so I just use a as |-63| = 63 and b as 23?

7. ok - but if I do that - wouldn't it screw up my end result? or would I then have to convert the x0 to be negative?

8. Originally Posted by cassiopeia1289
ok - but if I do that - wouldn't it screw up my end result? or would I then have to convert the x0 to be negative?
probably. just start over with the new insight that you have and run the algorithm through from scratch. what do you end up with? if it just changes the x to an initial negative result, so be it, just choose t so that you only produce positive x values

9. ok, so I got x0=4 and y0=11
the equation yields:
1 = 23(11) - 63(4)

should I make y0=(-4), making 63 positive, or keep y0=4, making 63 negative like it was before I did absolute values

If I undid it to begin with, shouldn't I have to redo it?

and either way - it doesn't make sense
I get: x = 4 + 23t > 0
and y = 11 - 63t > 0

even if I turn 63 negative or positive - they equal the same thing ... ? therefore no solutions?

10. Originally Posted by cassiopeia1289
ok, so I got x0=4 and y0=11
the equation yields:
1 = 23(11) - 63(4)

should I make y0=(-4), making 63 positive, or keep y0=4, making 63 negative like it was before I did absolute values

If I undid it to begin with, shouldn't I have to redo it?

and either way - it doesn't make sense
I get: x = 4 + 23t > 0
and y = 11 - 63t > 0

even if I turn 63 negative or positive - they equal the same thing ... ? therefore no solutions?
essentially it won't matter, since you could get the same solutions by choosing a different range for t, but, for consistency sake, you want to keep the 63 negative as that is how the problem started out

11. ok, but either way there are no integer solutions ...

12. Originally Posted by cassiopeia1289
ok, but either way there are no integer solutions ...
how so? x = 5, y = 14 work, for instance

your first solution was correct. i got it to be x = 5 + 23t and y = 14 + 63t. they cover the same thing

13. but the only reason I got 5 and 14 was because I was using the gcd to be -1 - which can't work
when I start over again, with positive numbers, I get the gcd to be 1 and x0=4 and y0=11, hence my problem

14. Originally Posted by cassiopeia1289
but the only reason I got 5 and 14 was because I was using the gcd to be -1 - which can't work
when I start over again, with positive numbers, I get the gcd to be 1 and x0=4 and y0=11, hence my problem
yes, that is because 1 = (-63)*4 + 23*11

but remember, we don't want the linear combination to be 1, we want it to be 7, so multiplying through by 7, we get 7 = (-63)*28 + 23*77

you got this last time, maybe you're just tired why you can't see it now

look back on your other post before this one, you did exactly what i just did

15. haha - wow - I keep forgetting to do that step, like on all my problems, its really would be humorous if it wasn't so sad

but still: even when x0=28 and y0=77, you get t > -28/23 and t > -77/63
which doesn't work because a) they're negative and b) there is no integer in between those intervals

however, it DOES work if I don't convert the 63 into a negative - then it works out perfectly ...

Page 1 of 2 12 Last