SOLUTION: Hello we recently learned about diophantine equations and how to use euclidean algorithm to solve it, but i am kind of really stuck! find all solutions to each of the following

Algebra ->  Coordinate Systems and Linear Equations  -> Lessons -> SOLUTION: Hello we recently learned about diophantine equations and how to use euclidean algorithm to solve it, but i am kind of really stuck! find all solutions to each of the following       Log On


   

Question 1019644: Hello we recently learned about diophantine equations and how to use euclidean algorithm to solve it, but i am kind of really stuck!
find all solutions to each of the following Diophantine equations:
24x+63y=99

how could i use the algorithm to solve this?
Answer by Fombitz(32388) About Me  (Show Source):
You can put this solution on YOUR website!
First find the GCD using the Euclidean algorithm,
63=2%2A24%2B15
24=1%2A15%2B9
15=1%2A9%2B6
9=1%2A6%2B3
6=2%2A3
So GCD=3.
Using back substitution,
3=9-1%2A6
3=9-1%2815-1%2A9%29=15-2%2A9
3=15-2%2824-1%2A15%29%29
3=8%2A24-3%2A63
So then,
n=8
m=-3
a=24
b=63
c=99
GCD=3