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

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.

-
Are $x,y \in \mathbb Z$? – dashdart 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

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

-

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.

-

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.

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