Question

Determine all integer solutions to 5x - 7y = 99. Professor says to watch the minus sign, having trouble with that.

Answer 1

this is very similar again to the ones you've already done

Answer 2

where are you getting stuck?

Answer 3

I'm getting stuck on the negative sign. AT what time during the continued fraction do I address the minus sign.

Answer 4

continued fraction? I just use simple algebra.

Answer 5

look at what I did in your question here: http://openstudy.com/updates/4fe615bee4b02c91101af1b3

Answer 6

Professor's example for x+y=z formulas for finding all integer solutions shows continued fraction, then using the solution obtained to plug into a formula for finding all (n) solutions.

Answer 7

do you have a web site link that describes this method?

Answer 8

it's in our book. I also came up with a different answer that seems to work for all (n) for the other problem, I'll post it there.

Answer 9

I haven't heard of the continued fraction method which is why I was interested in learning it

Answer 10

using 2x+11y=10

Answer 11

but I have solved this using the algebraic method I used in the previous question

Answer 12

what would the algebreic method yeild, and how would you do it?

Answer 13

shall I show you the solution to 2x+11y=10 using algebraic method?

Answer 14

continued fraction first asks for gcd (a,b), continued fraction table looks like this

77 14 7 0
5 2
0 1 5 11
1 0 1 12

Answer 15

where did the 77, 14, and 7 come from in the 1st row?

Answer 16

ah! King George is here!

Answer 17

King George - do you know about this "continued fraction" method - and where can I learn more about it?

Answer 18

i'd rather learn what to do in case of minus sign for continued fraction, which is what prof wants

Answer 19

I've never seen the continued fraction method.

Answer 20

@tim93 is there a formal name for this method?

Answer 21

77 = a, 14 = b, 7 is the remainder when 14 goes into 77, it continues out until 0 is reached

Answer 22

the next line represents the integer quotient

Answer 23

diophantine equations, euclidian algorithm for gcd, discrete math course

Answer 24

The bottom two rows are generated starting with 0,1 on first row, 1,0 on last row

Answer 25

ok - let me try and find more information on this method and then I'll try and see if I can solve this using this new method.

Answer 26

Oh wait, I have seen this. I've heard it called "The box method" or "The magic box method"

Answer 27

to find the next values, multiply the number above by the number to the left, and add the number two to the left

Answer 28

thanks @KingGeorge that might help me find more information on this.

Answer 29

@tim93 do you want to see how I solved this using the algebraic method as well or shall I come back once I've learnt this new continued fraction method?

Answer 30

now, start with positive on the bottom left, and count alternating negative and positive until you reach the second to last value on the right, this value corresponds to the upper left value, so you're left with one solution to the problem of
77*10 + 14*-50 = 70 (multiplied by ten because we had calculated one solution for 7 in the box)

Answer 31

yes, i'd love to see the algebraic solution, but for the original questuion in this thread, as you answered the other on the other thread, btw, thanks for that

Answer 32

ok, here goes...

Answer 33

\[\begin{align}
5x-7y&=99\\
\therefore x&=\frac{7y+99}{5}=\frac{2y+5y+4+95}{5}=\frac{2y+4}{5}+y+19\\
\implies 2y+4&=5n\\
\therefore y&=\frac{5n-4}{2}\implies n\text{ must be even}\\
\therefore n&=2m\\
\therefore y&=\frac{10m-4}{2}=5m-2
\end{align}\]

Answer 34

that gives all integer y's

Answer 35

now just substitute that back into the expression for x

Answer 36

to get:\[x=7m+17\]

Answer 37

so final solution is:
x = 7m + 17
y = 5m - 2
for all integer m

Answer 38

does that make sense?

Answer 39

how did you get from second to third line, and what happens to y + 19

Answer 40

ok, you understand this part:\[x=\frac{2y+4}{5}+y+19\]

Answer 41

solved for x, and factored

Answer 42

for x to be an integer, the fractional component on the RHS must also be an integer - agreed?

Answer 43

yes

Answer 44

therefore (2y+4) must be a multiple of 5

Answer 45

yes

Answer 46

that leads to:

2y + 4 = 5n

Answer 47

YES

Answer 48

clearer

Answer 49

all clear now?

Answer 50

in essence, it's inductive in reasoning? How to make the leap from the original equation to the second and third lines takes some practice i guess

Answer 51

yes - you are right - with lots of practice you learn to recognise things like this more easily

Answer 52

could we have left it without saying that n must be even?

Answer 53

I don't think so, because we end up with:\[y=\frac{5n-4}{2}\]which is not an integer for all n

Answer 54

yes

Answer 55

BTW: I found this site which I /think/ explains your profs method: https://docs.google.com/viewer?a=v&q=cache:SCODMwQYRgwJ:homes.ieu.edu.tr/skondakci/courses/CE340/modular-arithmetic.ppt+%22the+magic+box+method%22&hl=en&gl=uk&pid=bl&srcid=ADGEEShS_nIpT9WxRzxast7INR8shaAecRQschvqHbvVxPyJdb5Al5HRuihFNtM-vcFctxRE2PQBvF7OuGGKt-EKzUyV99DuiusiaHKAWUgtp1g3TLN6To-Qz6SqcFUE64AQtTzZMpz_&sig=AHIEtbTA8jwNcVwV33A9c7TYcqn3B6jctg

I am going to /try/ and learn this method - looks interesting

Answer 56

It will come in handy for me too, as this guy explains things somewhat briefly, and we are expected to learn beyond the six pages per chapter

Answer 57

I don't know if it says in that link or not, but the magic box method only works when the gcd is 1.

Answer 58

so the factors of x and y have to be coprime?

Answer 59

but it seemed to work for the equation in the other problem

Answer 60

The factors must be coprime.

Answer 61

ok - well I have plenty of reading to do then thanks to you two! :D

I'll get back to you once I have learnt this method.

Answer 62

Or at least, that's what I was taught in my classes.

Answer 63

once the cofactors are coprime, then once the box is solved, we'd multiply by some x to revert back to original equation maybe?

Answer 64

What was the other equation?

Answer 65

77 14 7 0 is the first line of the box, with 7 being gcd(77,14)

Answer 66

oops, i guess gcd has nothing to do with that line, it's just the remainder

Answer 67

coincidentally gcd

Answer 68

i would love it if someone showed me the box method for a negative as one of the factors, once a solution is reached, our prof gave us these two formulas, where s and t are one solution for x and y respectively, and d is gcd(a,b), and k is any integer

x=s + (a/d)k
y=t-(b/d)k

Answer 69

I'll work some stuff out and see if I can get a working example with some negative numbers. First though, what exactly do you mean by "a negative as one of the factors?" Do you mean something like \(23x-32y=1\)?

Answer 70

yes, and how does it fit into the box, if at all, perhaps it is disregarded until the next step

Answer 71

I've got to leave for a bit, but I'll post some stuff on that when I get back.

Answer 72

thanks George, for your dedication to MATH

Answer 73

I'll just put an example for \(23x+32y=1\) here. First, Euclidean algorithm.\[32=23\cdot1+9\]\[23=9\cdot2+5\]\[9=5\cdot1+4\]\[5=4\cdot1+1\]\[4=1\cdot4+0\]So the gcd is 1. Now create the table \[\begin{array}{|c|c|c|c|c|c|c|}
\hline &&1&2&1&1&4\\
\hline 0&1&1&2+1=3&3+1=4&4+3=7&28+4=32 \\
\hline 1&0&1&2&2+1=3&3+2=5&20+3=23 \\
\hline
\end{array}\]Therefore, you know that a solution is \[7(23)-5(32)=1.\]Notice that in the last two columns, we are multiplying diagonally to achieve the solution. Diagonally down will be positive, diagonally up will be negative.

Answer 74

Wouldn't you have to start the Euclidian algorith with 7 and -5 for the original equation, not 23 and 32?

Answer 75

No, we use the Euclidean Algorithm to find the gcd of 32, 23, and using the successive quotients, we can compute a solution to \(23x+32y=1\).

Answer 76

how would you draw up 5x - 7y = 99

Answer 77

Well, let's see here. \[7=5\cdot1+2\]\[5=2\cdot2+1\]\[2=1\cdot2+0\]Draw the table.\[\begin{array}{|c|c|c|c|c|}
\hline &&1&2&2\\
\hline 0&1&1&2+1=3&6+1=7\\
\hline 1&0&1&2&4+1=5\\
\hline
\end{array}\]So \(3(5)-2(7)=1\).

Answer 78

To find \(5x-7y=99\), just multiply by 99. That means \[5(297)-7(198)=99\]

Answer 79

did you use the magic box?

Answer 80

That may not be the simplest solution, but it is a solution.

I used the magic box to find a solution to \(5x-7y=1\). With that solution, I found the solution to \(5x-7y=99\).

Answer 81

so, in the box, do you use 7 or -7

Answer 82

I'm using 7 in the box.

Answer 83

You just have to remember that the very last multiplication, which is diagonally up, you should multiply by -1.