Wrong result with diophantine equation when there is subtraction

66 Views Asked by At

I have equation $966x-686y=70$ and I get the wrong solution every time when there is "-" in equation $ax\textbf{-by}=c$. I don't know where I am making a mistake.

And my solution seems like that:

step 1) $GCD(966,686) =14\\ 966= 1\cdot686+280\\686=2\cdot280+126\\280=2\cdot126+28\\126=4\cdot28+\color{red}{14}\\28=2\cdot14+0$

step 2) does $14|70$ ? Yes it does so there is solution

step 3) reverse Euclidean algorithm: $14=126-4\cdot28=1\cdot126-4(1\cdot280-2\cdot126)=9\cdot126-4\cdot280=\\9(1\cdot686-2\cdot280)-4\cdot280=9\cdot686-22\cdot280=9\cdot686-22(1\cdot966-1\cdot686)=\color{blue}{31}\cdot686\color{green}{-22}\cdot966=14$

SO: $\color{green}{-22}\cdot966+\color{blue}{31}\cdot686=14\quad |\cdot5\\\color{green}{-110}\cdot966+\color{blue}{155}\cdot686=70$

particular solution: $x_0=\color{green}{-110}\\y_0=\color{blue}{155}$

complete solution: $x=-110+\frac{-686}{14}\cdot t=-110-49\cdot t\\y=155-\frac{966}{14}\cdot t=155-69\cdot t\quad \textrm{where }t\in \mathbb{Z}$

But when i try check my solution with this tool here I get particular $x_0 = -110\\y_0 = -155$ and complete $x = -110 + 49t\\ y = -155 + 69t$

math formulas I use for complete solution: $x=x_0+\frac{b}{d}\cdot t\\y=y_0-\frac{a}{d}\cdot t$

1

There are 1 best solutions below

3
On BEST ANSWER

You have found $-22 * 966 + 31 * 686 = 14$, so $-110 * 966 + 155 * 686 = 70$.

However, the question does not ask for either of these. It's asking for $x$ and $y$ satisfying $966x - 686y = 70$.

Looking back at the equation we have derived : $-110 * 966 + 155 * 686 = 70$, it is NOT in the correct form, because of the $+$ sign in the middle.

Adding is the same as subtracting a negative, so we can rewrite it as $-110 * 966 - (-155) * 686 = 70$.

Now it's in the correct form, so we can solve it as $x = -110, y = -155$.