How to get a solution of $119x-71y=19$ in natural numbers?

Question

I'm trying to solve the following equation in natural numbers: $119x-71y=19$.

I used extended Euclid for this:

$119 = 71 \cdot 1 + 48$

$71 = 48 \cdot 1 + 23$

$48 = 23 \cdot 2 + 2$

$23 = 2 \cdot 11 + 1$

And then:

$1 = 23 - 11 \cdot 2$

$1 = 23 - 11 \cdot (48 - 23 \cdot 2)$

$\cdots$

$1 = -34 \cdot 119 + 57 \cdot 71$

So the roots are $x_0 = -646,\ y_0 = -1083$ if I'm not mistaken. So how to get the solution in natural numbers from this?

Answer 1

You have $119x_0-71y_0=19$. With $119x-71y=19$, you can have $$119(x-x_0)=71(y-y_0)$$ Since $119$ and $71$ are coprime, we have $$x-x_0=71k,\quad y-y_0=119k,$$ i.e. $$x=x_0+71k,\quad y=y_0+119k$$ where $k\in\mathbb Z$.