How Do You Solve Linear Diophantine Equations?

[Mattofix]

Homework Statement

I don't know where to start on this question - could someone please point me in the right direction so i can look up the method.

Q: Find integers x, y such that 45x + 63y = 99. Can we find integers s, t such that 45s +65t = 80? Either find them or prove they cannot exist.

 

[NateTG]

What have you tried?

 

[Mattofix]

when x = 5 and y = -2 , but that was just randomly trying things. is there any method or rule to this?

 

[Mystic998]

Look up the Euclidean algorithm. Also, if there are common factors in all the terms, it might be in your best interest to factor them out.

 

[astrosona]

these equations are just a equation of a linear line! both of them; so you can just plot the line and say you will have infinity answers for x and y which have to be on the line. considering both lines: of course these can encounter with each other and as they are not parallel their is exactly one point that is in their intercept (if you deal with x, y).

 

[Rainbow Child]

Homework Statement

I don't know where to start on this question - could someone please point me in the right direction so i can look up the method.

Q: Find integers x, y such that 45x + 63y = 99. Can we find integers s, t such that 45s +65t = 80? Either find them or prove they cannot exist.

The equations a\,x+b\,y=c are called Linear Diophantine Equations. If you acn find a particular solution (x,y)=(x_o,y_o) then you can find the general solution by writting x=x_o+\lambda\,t,\,y=y_o+\mu\,t. Plugging these to the original equation you determinate the values of \lambda,\,\mu.

You can easily proof that if c is not divisible by gcd(a,b) then there is no solution.