Applying Euclidean algorithm I got


$247=4\cdot 52+39$


$39=3\cdot 13+0$

Applying this in reverse order I got


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


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

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

  • $\begingroup$ Okay as you wish. $\endgroup$ Commented Nov 28, 2015 at 15:19
  • $\begingroup$ @Vikram The diophantine equation tag is absolutely appropriate for this question. You are looking for integral solutions to a polynomial equation. $\endgroup$ Commented Nov 28, 2015 at 15:20
  • $\begingroup$ You could add 247 to x and subtract 299 from y $\endgroup$
    – Empy2
    Commented Nov 28, 2015 at 15:21
  • $\begingroup$ @PeterWoolfitt, this question is from the 1st chapter of dudley, whereas diophantine is 3rd chapter $\endgroup$
    – Vikram
    Commented Nov 28, 2015 at 15:22
  • $\begingroup$ @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 :) $\endgroup$ Commented Nov 28, 2015 at 15:31

3 Answers 3


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

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

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

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



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


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

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


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .