2

Having the equation:

$$35x+91y = 21$$

I need to find its general solution.

I know gcf $(35,91) = 7$, so I can solve $35x+917 = 7$ to find $x = -5, y = 2$. Hence a solution to $35x+91y = 21$ is $x = -15, y = 2$.

From here, however, how do I move on to finding the set of general solutions? Any help would be very much appreciated!

Cheers

Amzoti
  • 56,093
MrD
  • 416

4 Answers4

3

You really ought to have checked your particular solution, because it isn’t one:

$$35(-15)+92\cdot2=-343\;,$$

not $21$. Divide the original equation by $7$ to get $5x+13y=3$. By inspection $x=-2$, $y=1$ is a solution. Suppose that $x=-2+a$, $y=1+b$ is also a solution. Then

$$5(-2+a)+13(1+b)=3\;,$$

so

$$-10+5a+13+13b=3\;,$$

and therefore $5a+13b=0$. Thus, $b=-\frac5{13}a$. Since $a$ and $b$ must be integers, this says that $a$ must be a multiple of $13$. Say $a=13k$. What does that make $b$? Can you now write down the general solution in terms of $k$?

Brian M. Scott
  • 616,228
  • Does this say that b = -5k and a = 13k so x = -2+13k and y = 1-5k? – MrD May 17 '13 at 15:18
  • @user1876047: it does indeed. And the reasoning that I used here can be applied in general, though the fact that $5$ and $13$ are relatively prime did simplify matters a little. – Brian M. Scott May 17 '13 at 15:23
  • Ok thank you, I think this is a lot clearer for me now and congruency equations are as well consequently! :) Thank you very much for your help! :D – MrD May 17 '13 at 15:29
  • @user1876047: You’re very welcome! – Brian M. Scott May 17 '13 at 15:29
  • I was just wondering, would you have any list of online similar excersises (with answers) to suggest? The ones given by my professor are quite limited in number and I know the solutions by heart :\ – MrD May 17 '13 at 15:32
  • @user1876047: I don’t, I’m afraid. You might try searching on linear diophantine equations; I don’t know whether you’ll find any problem sets, but I do know that you’ll find a number of solved examples in various people’s lecture notes. – Brian M. Scott May 17 '13 at 15:38
  • Ok, thanks anyway :) – MrD May 17 '13 at 15:48
2

Hint: If $35x + 91y = 21$ and $35x^* + 91y^* = 21$ for for some $(x,y)$ and $(x^*, y^*)$, we can subtract the two equalities and get $5(x-x^*) + 13(y-y^*) = 0$. What does this tell us about the relation between any two solutions?

Now, $5$ and $13$ share no common factor and we're dealing with integers, $13$ must divide $(x-x^*)$. In other words, $x = x^* + 13k$ for some integer $k$ and substituting it into the equality yields $y = y^* - 5k$. Thus, once you have one solution $(x^*,y^*)$, all of them can be expressed as $(x^*+13k, y^*-5k)$.

Peter Košinár
  • 10,810
  • So if we have 35x-35x+91x-91x= 0 I get 35(x-x) - 13(y-y) = 0, which is 35(x-x) = 13(y-y). This tells me that y* = y - 35/13(x-x), and x = x - 13/35(y-y*) but this doesn't really tell me much... – MrD May 17 '13 at 14:42
1

After dividing the equation by the $\gcd$, you get $5x + 13y = 3$, which is equivalent to $5x = 3\pmod {13}$. Solving, $x = 11\pmod {13}$. Substitute $x = 11 + 13t$ into the equation and get $y = -4 - 5t$ which is the complete solution.

Tianlalu
  • 5,177
John Butnor
  • 74
1

On division by $7$ we get $5x+13y=3$

Now, by observation $13-5\cdot2=3$

So, $5x+13y=3=13-5\cdot2$

$\implies 5(x+2)=13(1-y)\implies \frac{5(x+2)}{13}=1-y$ which is an integer

$\implies 13$ divides $5(x+2)$

$\implies 13$ divides $(x+2)$ as $(5,13)=1$

So, $x+2=13a$ where $a$ is any integer, $x=13a-2$

So, $13y=3-5x=3-5(13a-2)=13(1-5a)\implies y=1-5a$

We can use the convergent property to a continued fraction as follows:

$$\frac{13}5=2+\frac35=2+\frac1{\frac53}=2+\frac1{1+\frac23}=2+\frac1{1+\frac1{\frac32}}=2+\frac1{1+\frac1{1+\frac12}}$$

So, the previous convergent of $\frac{13}5$ is $2+\frac1{1+\frac11}=\frac52$

$\implies 13\cdot2-5\cdot5=1$

So, we can write $5x+13y=3=3(13\cdot2-5\cdot5)$

Can you take it from here?

lab bhattacharjee
  • 274,582