Solution for $46x + 10y=2$ for $\{ x,y\} \in \mathbb{Z}$

Question

I've searched many youtube videos to help me solve them and although I have understood the concepts (using euclidean algorithm) I can't seem to get this right. I'd would prefer the answer to have all steps and explanations along the way, thanks.

Answer 1

This is a actually a pretty straightforward application of the euclidean algorithm. First we want to find gcd(10,46). Since 10 = 2*5 and 46 is not divisible by 5, the gcd is 2. So we know that there are integers x,y such that 46x+10y=gcd(10,46).

So we do the euclidean algorithm: $$ 46 = 4(10)+6$$ $$ 10 = 1(6) + 4$$ $$ 6 = 1(4)+2$$

Now we reverse the steps to get our equation. $$ 6-1(4) = 2$$ $$ 6-1(10-1(6))=2$$ Note:We replace 4 = 10-1(6) and rewrite as $$ 2(6)-10 =2$$ $$2(46-4(10)-10 = 2$$ Here we replace 6 = 46-4(10) and rewrite as $$(2)46-(9)10 = 2$$ Thus x =2 and y = -9.$\checkmark$

Answer 2

The given equation is equivalent to $$23x+5y=1$$

We see that $$ 23(2)+5(-9)=1$$ so $x=2$ and $y=-9$ is one solution.

We notice that we may consider $$x=2+5k$$ and $$y=-9-23k$$ for $k=0, \pm 1, \pm 2,....$ to get all solutions to the equation.

Answer 3

The fastest way consists in performing the extended Euclidean algorithm. The equation is equivalent to solving $$23x+5y=1,$$ which is a Bézout's relation between $23$ and $5$: \begin{array}{rrrl} r_i &x_i &y_i&q_i\\ \hline 23&1&0\\ 5&0&1&4 \\ \hline 3&1&-4&1 \\ 2 &-1&5&1\\ 1&\color{red}2&\color{red}{-9}\\ \hline \end{array} so a basic solution is $\;x=2,\;y=-9$. Doing some arithmetic and using Gauß' lemma shows the general solution is given by $$x=2+5k,\quad y=-9-23k\quad(k\in \bf Z).$$

Answer 4

Cancelling $\,2\,$ yields $\ 23x+5y = 1\iff\bmod\color{#c00} 5\!:\,\ 23x\equiv 1\iff x \equiv \dfrac{1}{23}\equiv \dfrac{6}3\equiv\color{#c00} 2$

So $\ x = \color{#c00}{2+5}n\ \Rightarrow\ y = \dfrac{1\!-\!23x}5 = \dfrac{-45\!-\!23(5n)}5 = -9\!-\!23n$

Answer 5

This was the method I first learned for tackling diophantine equations in terms of $x$ and $y$. There's a nice little theorem that comes along with it.

Theorem: Given an equation of the form$$ax+by=c$$where $a,b,c\in\mathbb{Z}$ and $\alpha,\beta$ are integral values of $x, y$ respectively, the general case takes the form$$\begin{align*}x & =\alpha-bt\\y & =\beta-at\end{align*}$$where $t$ can be an arbitrary integer.

The procedure, meanwhile, is repetitive. If $\alpha,\beta$ cannot be easily found by inspection, then divide by the smallest coefficient and split up the improper fractions if necessary. Equate the remaining fractions to an unknown variable and solve the remaining diophantine equation. If the solutions still cannot be found by inspection, repeat until you can.

I'll walk you through with this example:$$23x+5y=1$$Since five is the smallest coefficient, divide to get that$$4x+\frac 35x+y=\frac 15$$The remaining fractions are $\tfrac 35$ and $\tfrac 15$. Setting them equal to another unknown, we'll call $z$, we get$$\frac 35x=\frac 15+z\quad\implies\quad 3x=1+5z$$Here, it's easy to see that $z=1$ and $x=2$ are integral solutions. Now that we've found our value of $x$, it's time to substitute it into the original equation to find that $y=-9$. Hence, one value for $\alpha$ and $\beta$ are$$\begin{align*}\alpha & =2\\\beta & =-9\end{align*}$$

Therefore, by our theorem, the rest of the solutions will take the form$$\begin{align*}x & \color{blue}{\,\,=2-5t}\\y & \color{red}{\,\,=23t-9}\end{align*}$$