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

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?

• Okay as you wish. Commented Nov 28, 2015 at 15:19
• @Vikram The diophantine equation tag is absolutely appropriate for this question. You are looking for integral solutions to a polynomial equation. Commented Nov 28, 2015 at 15:20
• You could add 247 to x and subtract 299 from y Commented Nov 28, 2015 at 15:21
• @PeterWoolfitt, this question is from the 1st chapter of dudley, whereas diophantine is 3rd chapter Commented Nov 28, 2015 at 15:22
• @Vikram Regardless of where it is defined in the book, this is a question about diophantine equations and should be tagged as such. I'm sure you will agree after reading chapter 3 :) Commented Nov 28, 2015 at 15:31

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$.

• @someone: $299\times 5+247\times (-6)=13$. Commented Nov 28, 2015 at 15:28
• @someone he is right, I've got exactly the same solution Commented Nov 28, 2015 at 15:28

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}$

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.