Finding general solution using Euclid's extended algorithm

112 Views Asked by At

I have a problem where I'm supposed to find the general equation to $242x+1870y=66$.

I used Euclid's extended algorithm to find $x=8$ and $y=-1$, but am not sure how to find all possible solutions using this information.

Is there a formula I can plug into? or can someone assist me in finishing this problem?

1

There are 1 best solutions below

0
On

Hint: Consider the homogenous equation ($242x + 1870y = 0$). Perhaps, the solutions to your equations are exactly the sum of your particular inhomogenous solution and a solution to the homogenous problem, since the equations are linear. (prove it!)

Now note that you can multiply both sides of the homogenous equation ad libitum to generate all solutions.