Euclidean Algorithm Problem finding solutions

Question

Which of the following integers can be $x$, where $57x + 18y = 3$?

$a) 4$ $b) 5$ $c) 6$ $d) 7$

I've been told that solutions to $57x + 18y = 3$ are given by $x = 1+ \frac{18}{3} k$ and $y= −3− \frac{57}{3} k$.

Why is this the case and where did '$k$' come from?

Thanks

Answer 1

with $x=7$ we get $$18y=3-57\cdot 7$$ thus $$y=-22$$ the solution of your equation is given by $$x=1+6k,y=-3-19k$$ where $k$ is an arbitrary integer number $k$ is supposed to be an integer number and plug in your given solution $$57(1+6k)+18(-3+19k)=57-54+19\cdot18k-6\cdot 57k=3+(19\cdot 18k-6\cdot 57k)=3$$ there are infinity many Solutions and this indicates the Parameter $k$

Answer 2

There's an infinite number of solutions and $k$ can be any integer. If $k = 0$ then $x = 1$ and $y = -3$ is a solution. If $k= 1$ then $x = 7$ and $y = -22$ is a solution. And so on.

The thing is if $a, b$ are a solution so that $57a + 18b = 3= \gcd(57,18)$.

Then, for any integer $k$ we have:

$57(a + \frac {18}{\gcd(57,18)}k) + 18(b - \frac {57}{\gcd(57,18)}k) =$

$57(a + \frac {18}{3}k) + 18(b - \frac {57}{3}k) =$

$57(a + 6k) + 18(b - 19k)=$

$ 57a + 57*6k + 18b -18*19k + 18b =$

$57 a + 18b + (57*6k - 18*19k) =$

$57a + 18b + (\frac {57*18}3k - \frac {18*57}3 k) =$

$ 57a + 18b =$

$ 3$.

So if $(a,b)$ are a solution then $(a + \frac {18}3k, b - \frac {57}3k)= (a + 6k, b-19k)$ is also a solution.

So the question isn't "where did the $k$ come from"; it's "where did the $1$ and $-3$ come from".

......

There were the "simplest" solutions (closest to $x$ and $y$ being equal and/or one of the values closest to zero). You get these by Euclid algorithm: $18$ goes into $57$ three times with a remainder of $3$ so $57*(1) + (-3)*18 = 3$.

But that is only one solution. There are an infinite number of solutions. $(1 + 6k, -3 -19k)$. (The "$+ 6k$" will increase the equation by $57*6$ and the $-19k$ will decrease the equation by $19*18$ ... and $57*6= 19*18$.)

====

As this is multiple choice I wouldn't bother trying to solve all possible solutions but just check if the given choices work.

$57x + 18y = 3$

$57x = 3-18y$

$x = \frac {3-18y}{57} = \frac {1-6y}{19}$

And I would check which of $y = 4,5,6,7$ result in an integer. (If $y = 4 $ then $\frac {1-6y}{19} = -\frac {23}{19}$ and it is not a solution.

But $x = 7$... which agrees with the equation above.

Answer 3

$57x+18y=3$ when solved for $y$ gives $y=-\frac{57}{18}x+\frac{3}{18}$ which when simplified gives $y=-\frac{19}{6}x+\frac{1}{6}$ This is a linear equation with slope $-\frac{19}{6}$ and we can see that a solution integer pair is $(1,-3)$ So you can generate all integer pairs using this point and that slope! The rise effects the y and the run effects the x. So all the other integer pairs are $(1+6k,-3-19k)$

Answer 4

Everything starts with a Bézout's relation between $57$ and $18$: $$ 1\cdot 57-3\cdot 18=3. $$ Thus you have the obvious solution $$x_0=3, \quad y_0=-9.$$ Now suppose $(x, y)$ is another solution. Subtracting from the relation $\;57x+18y=3$ the above relation, you obtain the basic solutions: $$57(x-3)+18(y+9)=0\iff 19(x-3)=-6(y+9).\tag{1}$$ Thus $19$ is a divisor of $6(y+9)$. As $19$ and $6$ are coprime, Gauß' lemma implies that $19$ is a divisor of $y+9$, i.e. there exists an integer $k$ such that $$y+9=19k. $$ Similarly, $6$ is a divisor of$x-3$, i.e; the exists an integer $\ell$ such that $$x-3=6\ell.$$ Furthermore, rewriting $(1)$ with these data, we see that $\ell=-k$, so that finally $$x=3-6k,\quad y=-9+19k.$$