Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Find all integer solutions to $7595x + 1023y=124$

Using the Euclidean algorithm I have found the $\gcd(7595,1023)=31$ and found the Bezout identity $31=52\cdot1023-7\cdot7595$ but I'm not really sure how to go about finding all solutions to that equation.

I believe you can divide the equation through by the $\gcd$ - which gives $245x+33y=4$ - but I'm not sure what to do next.

share|cite|improve this question
Are $x,y \in \mathbb Z$? – funktor Aug 14 '12 at 14:34
Yes, $x,y \in \mathbb Z$ – Arvin Aug 14 '12 at 14:36
Find some $(x_0, y_0)$ that is a solution of $ax+by=c$. The general solution is $$ x=x_0+\frac{b}{\operatorname{gcd}(a,b)}\cdot t $$ $$ y=y_0-\frac{a}{\operatorname{gcd}(a,b)}\cdot t $$ where $t\in\mathbb{Z}$ – Norbert Aug 14 '12 at 14:37
It is enough to find a particular solution in order to get all of them. This particular solution can be given by Wolfram. – Piquito Jun 16 at 16:03
up vote 2 down vote accepted

From your remark $31 = 52\times 1023-7\times7595$, you get $124=4\times 31 = 7595\times(-4\times7)+1023\times(52\times 4)$, so you have a first solution $x_0=-28$ and $y_0=208$. So you have $7595(x-x_0)+1023(y-y_0)=0$, or $245(x-x_0) = - 33(y-y_0)$ (*). Now $245$ and $33$ are coprime, so for this equality to hold, you need to have: $$ x-x_0=33\lambda\\ y-y_0=245\mu $$

When you replace this into (*), you get $\lambda = -\mu$, so at the end the solution is given by: $$ x=33\lambda+x_0\\ y=-245\lambda+y_0 $$ Where $\lambda\in\mathbb{Z}$.

share|cite|improve this answer

Hint $\ $ For $\rm A\:$ linear, $\rm\ A\:X_1\! = B = A\:X_2 \ \iff\ 0 \:=\: A\:X_1\! - A\:X_2 = A\:(X_1\!-X_2)$

This implies that the general solution of $\rm\,\ A\:X = B\,\ $ is the sum of any particular solution plus a solution of the associated homogeneous equation $\rm\ A\:X = 0.\:$ This property holds true for every linear operator, e.g. for matrices, linear differential equations, linear recurrences, etc, a fact which will come to the fore if you study linear algebra and vector/affine spaces, modules, etc.

share|cite|improve this answer

You are looking for all solutions to

$245x + 33y = 4$,

or equivalently, all $x$ such that

$4 - 245x \equiv 0 \mod 33$,

which is equivalent to

$4 - 14x \equiv 0 \mod 33$,

since $245 \equiv 14 \mod 33$.

Pick one solution, say $x_0$, $x_k = x_0 + 33k$ will also be a solution, since $lcm(14, 33)/14 = 33$. This is the exact characterization of the solutions.

share|cite|improve this answer
"$4 - 245x \equiv 0 \mod 33$, which is equivalent to $4 + 9x \equiv 0 \mod 33$, since $245 \equiv -9 \mod 33$." This is wrong, for example if $x=1$, $4-245x = -241 = 23 \mod 33$, but $4+9x=13\mod 33$. – S4M Aug 14 '12 at 14:49
@S4M: thank you – gt6989b Aug 14 '12 at 18:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.