Find two integers $x$ and $y$ such that $15x+28y=1$

204 Views Asked by At

I tried to solve it using the Euclidean algorithm but after finding the gcd$(15, 28)=$ $1$, and reversing the steps of the Euclidean algorithm I get the following expression:

These are the reversal steps: $$13=2\times6+1$$ $$1=13-(2\times6)$$ $$1=13-6\left(15-13\right)$$ $$1=28-15-6\left(15-13\right)$$ $$1=28-15\left(1+6\right)+6\text{·}13$$

The expected result should be some expression of the form $$1=28\left(y\right)-15\left(x\right)$$

4

There are 4 best solutions below

0
On BEST ANSWER

$1=13-6\times2=13-6(15-13)=7\times13-6\times15=7\times(28-15)-6\times15$

$=7\times28-13\times15$

0
On

You already replaced a 13 by $$13=28-15$$

Why don't you replace the last 13 also by this?

It would have been faster if you combined the 13's together before replacing.

0
On

The fast method uses the extended Euclidean algorithm, based on the observation that all reminders in the Euclidean algorithm can be written as a linear combination of $15$ and $28$, with a recursive relation deduced from the relation step $i$: $$ r_{i-1}=q_i r_i+r_{i+1}\iff r_{i+1}= r_{i-1}-q_i r_i,$$ from which we deduce the relations (with obvious notations) $$ x_{i+1}= x_{i-1}-q_i x_i,\qquad y_{i+1}= y_{i-1}-q_i y_i.$$ As it is a recursion of order $2$, we have to set the initial values $r_0=15$, $r_{-1}=28$, whence the following layout:

\begin{array}{rrrl} r_i &x_i&y_i&q_i \\ \hline 28 & 0 & 1 \\ 15 & 1 & 0 & 1 \\ \hline 13 & -1 & 1 & 1 \\ 2 & 2 & -1 & 6 \\ \color{red}1 & \color{red}{-13} & \color{red}{7} \\ \hline \end{array}

0
On

Applying the Euclidean algorithm we have $$28=1\cdot15+13$$ $$15=1\cdot13+2$$ $$13=6\cdot2+1$$ $$2=2\cdot1+0$$

So we have $\gcd(13,28)=1$ and for the reversal steps $$1=13-6\cdot2$$ and now substituting the second $$2=15-1\cdot 13$$ we have $$1=13-6\cdot2=13-6\cdot(15-1\cdot13)=7\cdot13-6\cdot15$$ and finally substituting the first $13=28-1\cdot15$ we obtain $$1=7\cdot13-6\cdot15=7\cdot(28-1\cdot15)-6\cdot15$$ $$=7\cdot28-13\cdot15$$

Thus $$7\cdot28-13\cdot15=1$$