Finding general solution using Euclid's extended algorithm

Question

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?

divide through by 22, $11x+ 85y= 3.$ Since $11$ and $85$ are coprime, all solutions come from one seed solution, then add any multiple of $85t$ to $x,$ giving $x +85t,$ and replace $y$ by $y - 11t$ — Will Jagy, Feb 23 '21 at 22:13

score 1 · Answer 1 · answered Feb 23 '21 at 22:17

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.

Finding general solution using Euclid's extended algorithm

1 Answers1