General Solution of Diophantine equation

Question

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

Answer 1

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

Answer 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)$.

Answer 3

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?