2
$\begingroup$

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.

  • 0
    It is enough to find a particular solution in order to get all of them. This particular solution can be given by Wolfram.2016-06-16

3 Answers 3

2

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

4

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.

2

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.