0
$\begingroup$

This is the working to find the gcd using the Euclidean algorithm $$\begin{align}1820 &= 7(231) + 203 & (a) \\ 231 &= 1(203) + 28 &(b)\\ 203 &= 7(28) + 7 &(c)\\ 28 &= 4(7)+0 &(d)\\ \end{align}$$

The last non-zero remainder is 7, so gcd(1820, 231) = 7.

And then to find linear combination m and n:

$$\begin{align} 7 &= 203 − 7(28) &\mathrm{from}\ (c) \\ &= 203 − 7(231 − 203) &\mathrm{from}\ (b) \\ &= (−7)(231) + 8(203) \\ &= (−7)(231) + 8(1820 − 7(231)) &\mathrm{from}\ (a)\\ &= 8(1820) + (−63)(231)\\ \end{align} $$

However I'm confused at the linear combination line where it has = (−7)(231) + 8(203). Where did the 8 come from in this line? There was no 8 in the previous line.

$\endgroup$
5
  • 2
    $\begingroup$ 203-7(231-203) = 203-7*231+7*203 = (-7)*231+8*203 might be what you're looking for? (Also, in a post where you're using expressions like 8(203) to denote multiplication, using (2), (3), etc. for line markers is downright cruel...) $\endgroup$ Commented Aug 15, 2019 at 20:45
  • 1
    $\begingroup$ The $8$ comes from $(1+7)$ [times $203$] $\endgroup$ Commented Aug 15, 2019 at 20:47
  • 1
    $\begingroup$ The previous line was $7 = 203 - 7(231 - 203)$. Expand the out. $203 - 7(231-203) = 203 - 7*231 + 7*203 = 203 + 7*203 - 7*231 = 203(1 + 7) - 7*231 = 203*8 - 7*231$. That's where it came from. $\endgroup$ Commented Aug 15, 2019 at 21:59
  • $\begingroup$ "Where did the 8 come from in this line? There was no 8 in the previous line." No... but there was as $203 - 7(-203)$ in the previous line :) $\endgroup$ Commented Aug 15, 2019 at 22:01
  • $\begingroup$ The reason you're having difficulty is because this is an extremely poor method to extend the Euclidean algorithm. Instead you should use this method which is much simpler so much less error-prone. $\endgroup$ Commented Aug 16, 2019 at 0:39

1 Answer 1

Reset to default
1
$\begingroup$

The extended Euclidean algorithm is more easily done this way, in tabular form:

$$\begin{matrix} 1820 & 1 & 0 & -\\ 231 & 0 & 1 & 7 \\ 203 & 1 & -7 & 1 \\ 28 & -1 & 8 & 7 \\ 7 & 8 & -63 & 4 \\ 0 & (-33) & (260) & - \\ \end{matrix}$$

where the first column are the remainders you computed, the final column the quotients, and the two in the middle are the coefficients of $1820$ and $231$ respectively.

To compute 203 we do $1820 - 7 \times 231$ so the coefficients are found using the same relation on the previous rows: a row with $1$ and $0$ (for $1820$) minus 7 times the row with $0$ and $1$, giving $1$ (for $1 - 7 \times 0$) and $-7$ (for $0 - 7 \times 1$) hence the third row. 203 goes once into 231 so we have $0\ 1$ minus $1$ times $0 \ -7$ giving $-1 \ 8$.

We go on that way (e.g. $-63 = -7 - 7 \times 8$ etc.) until we reach $0$ on the left (no need to do those coefficients; I put them between braces) and then the row before it has the gcd and its coefficient combination:

$$7 = 8 \times 1820 + (-63) \times 231$$

This avoids the error-prone back-substitutions and is easy to program.

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.