Find two solutions of $299x+247y=13$

Question

Applying Euclidean algorithm I got

$299=247+52$

$247=4\cdot 52+39$

$52=39+13$

$39=3\cdot 13+0$

Applying this in reverse order I got

$52-39=13$

$52-(247-4\cdot 52)=13$

$5(299-247)-247=13$

$5\cdot 299-6\cdot 247=13$

$x=5, y=-6$, this is one solution, what is the other solution?

Answer 1

You know $$5\cdot 299-6\cdot 247=13.$$ So, you can have $$299x+247y=13=5\cdot 299-6\cdot 247,$$ i.e. $$299(x-5)=247(-6-y)$$

Dividing the both sides by $13$ gives $$23(x-5)=19(-6-y)$$ Since $23$ and $19$ are coprime, we have $$x-5=19k,\quad -6-y=23k,$$ i.e. $$x=19k+5,\quad y=-23k-6$$ where $k\in\mathbb Z$.

Answer 2

As $13|(299,247)=13$

from this, we shall have $13$ in-congruent solutions $\pmod{13}$

$299x+247y=13\iff23x+19y=1=23\cdot5-19\cdot6$

$\iff23(x-5)=-19(y+6)$

As $\dfrac{19(y+6)}{23}=5-x$ which is an integer,

$\implies23\mid(y+6)$ as $(19,23)=1$

$\iff y\equiv-6\pmod{23}$

and similarly, $x\equiv5\pmod{19}$

Answer 3

Consider an integral solution $(x_0,y_0)$ to the diophantine equation

$$c=ax+by$$

So we have $$c=ax_0+by_0$$

To generate (infinitely many) more solutions we can just apply an algebraic trick

$$c=ax_0+by_0+abd-abd=a(x_0+bd)+b(y_0-ad)$$

Choosing any $d\in\Bbb{Z}$ gives the solution pair $(x_0+bd,y_0-ad)$ and choosing $d=0$ gives the original solution.