Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Are $x,y \in \mathbb Z$? –  Bidit Acharya Aug 14 '12 at 14:34
    
Yes, $x,y \in \mathbb Z$ –  Arvin Aug 14 '12 at 14:36
1  
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}$ –  no identity Aug 14 '12 at 14:37

3 Answers 3

up vote 1 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|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|improve this answer
1  
"$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

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|improve this answer

Your Answer

 
discard

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.