# Find the general solution to diophantine equation $-221x + 187y - 493 = 0$

I have to find the general solution to

$$-221x + 187y - 493 = 0$$ The main issue, I'm figuring out if I have found the general solution or not. Below, are my steps:

The $\gcd{(-221,187)} = 17$ and $\gcd{(-221,187)} \mid -493 = -29$.

\begin{align} &221 = 187 + 34 \\ &187 = 34(5) + 17 \\ &34 = 17(2) \end{align}

Then from here, I go in reverse and do the following:

\begin{align} 17 &= 187 - 34(5) \\ &= 187 - 5(221 - 187) \\ &= 187 - 5(221) + 5(187) \\ &= -5(221) + 6(187) \\ &= 221(-5) + 187(6) \end{align}

Then from here, I rearrange the equation to get

$$221(-5) + 187(6) - 17$$

However, this doesn't resemble my original equation, so I have to multiple everything by $29$ to get

$$-221(145) + 187(174) - 493 = 0$$

So now my $x$ equation should be in the form of $x = x_0 + jb$ and $y = y_0 - ja$, where $j \in \mathbb{Z}$. My general solution should be:

\begin{align} &x = 145 + \frac{174}{29}j = 145 + 11j \\ &y = 174 - \frac{-221}{29}j = 174 + 13j \end{align}

So, is that correct and is this how you would solve these linear Diophantine equations?

Thanks a lot!

• Looks ok on quick glance. You can find a simpler and less error-prone way to do the Extended Euclidean algorithm in this answer. – Bill Dubuque Apr 6 '14 at 21:32

As far as I know, Cauchy gave the [first] general solution:

Theorem (Cauchy). If $r,s,t$ are relatively prime integers, the complete solution to $$rX+sY+tZ=0$$ in integers $x,y,z$ is given by $$(x,y,z) = (s\delta-t\beta,\ t\alpha-r\delta,\ r\beta-s\alpha),$$ where $\alpha, \beta,\delta$ are arbitrary integers.

Your problem is then, as you point out, handled by Cauchy's after dividing out the gcd of $17$.

• Do you have a reference for this theorem? – user119264 Nov 1 '16 at 4:38
• Exercises de math., 1, 1826, 234. Oeuvres de Cauchy, (2), 6, 1887, – Kieren MacMillan Nov 1 '16 at 9:30

[For the following paragraphs, please refer to the figure at the end of the last paragraph (the figure is also available in PDF).]

The manipulations performed from steps (0) to (14) were designed to create the linear system of equations (0a), (6a), and (14a). The manipulations end when the absolute value of a coefficient of the latest equation added is 1 (see (14)).

It is possible to infer equations (0a), (6a) and (14a) from (0), (6) and (14) respectively without performing manipulations (0) to (14) directly. In every case, select the smallest absolute value coefficient, generate the next equation by replacing every coefficient with the remainder of the coefficient divided by the selected coefficient (smallest absolute value coefficient) – do the same with the right-hand constant – and add the new variable whose coefficient is the smallest absolute value coefficient. If the new equation has a greatest common divisor greater than one, divide the equation by the greatest common divisor (it may be necessary to divide this greatest common divisor from previous equations). Stop when the absolute value of a coefficient of the latest equation added is 1.

Then proceed to solve the linear systems of equations.