Question

All integer solutions to a Diophantine equation using the euclidean algorithm.

Answer 1

Hello. I'm struggling to understand the reasoning to get to all sln's of a diophantine equation like 3x+5y=1

first i do 5=3+2
3=2+1
2=2(1)

hcf(5,3)=1

3x+5y=1
1=3-2
1=3-(5-3)
1=(2)3-5

x=2
y=-1

now i understand that x=2+5t and y=-(1+t)
but how do i get to that answer?

Answer 2

y=-(1+3t)

Answer 3

I'm not sure I understand your question. To me it looks like you did all the work required to get to the answer.

Answer 4

yes i did. but i do not understand the logical leap from 1 solution to all solutions. i can do it but i don't understand why it works

Answer 5

Well let's plug in the general solution, and see what happens.

Using \(x=2+5t\) and \(y=-1-3t\), and just plugging these values in, we get\[3(2+5t)+5(-1-3t)=6+15t-5-15t=1.\]So we see that any value of \(t\) that we choose, will still give us what we want. Since we specifically want integer solutions, we then restrict \(t\) to the integers.

Answer 6

that stands to reason :)

the way i saw it being done was

x=2, y=-1
3(x-2)=5(y+1)
x-2=5m
x=5m+2

and i think this is because of the fundementasl theorem of arithmatic x-2 must be a multiple of 5. but then i don't understand how to use this to solve for y

Answer 7

To get \(y\), you can do two things. First, just do the same process you just did, except with \(y\) instead of \(x\). The only issue you might have, is that the solutions might be offset. I.e., you might get \(x=5m+2\) and \(y=-3m+2\) or something like that. You'll notice that plugging in any value for \(m\) in this case will not give you what you want. You just have to rectify one of the equations by either adding or subtracting either 3 or 5. So you could subtract 3 from \(-3m+2\), or subtract 5 from \(5m+2\), and now everything works again.

Answer 8

3x+5y=1
3(5m+2) +5y=1
15m+6+5y=1
15m+5y=-5
5y=-5-15m
y=-1-3m

oh. i just subbed x=5m+2 into an earlier equation and it worked.

Answer 9

The second way is exactly what you just posted :)

Answer 10

thankyou. it helps to have the help. :)