find integers n m such that

find integers m and n such that gcd(258,180 ) = 258m + 180n

so far I have

258 = (1) 258 + (0) 180

180 = (0) 258 + (1) 180

78 = (1) 258 - (1) 180

-54 = (1)180 - 3(78)

however, im abit stuck once I get to this point

• You have to use euclidean algorithm to write gcd as linear combination. Commented Nov 7, 2019 at 6:14
• I assume you meant $258$ when you typed $250$ Commented Nov 7, 2019 at 6:29
• I added an answer showing how to complete yoru calculation. This is much easier (and less error prone) than the backward methods in the other answers. Commented Nov 7, 2019 at 16:33

You don't have to but it's a good idea to avoid negative values.

$$258 = 1*180 + 78$$

$$180 = 2*78 + 24$$

$$78 = 3*24 + 6$$

$$24 = 4*6 + NOTHING$$

So that is as far we can go. $$\gcd(180,258) = 6$$-- as $$6|180$$ and $$6|258$$ but nothing larger than $$6$$ divides both.

So we want $$258m + 180n = 6$$

And we have $$6 = 78 -3*24$$.

But $$24 = 180 - 2*78$$ so $$6 = 78 -3(180 - 2*78)$$.

And $$78 = 258 - 180$$.

So $$6= (258-180) - 3(180 - 2*(258-180))$$.

And that's it.

$$6 = (258 - 180) - (3*180 -6(258 - 180))=$$

$$258 - 180 - 3*180 + 6(258 -180) =$$

$$258 - 180 -3*180 + 6*258 - 6*180 =$$

$$7*258 - 10*180$$

So $$m=7$$ and $$n=-10$$.

.......

Oh I forget to mention that $$m=7$$ and $$n=-10$$ are not that only such integers of course.

$$180 = 6*30$$ and $$258 = 6*43$$

And $$6=258*7 +180*(-10) =$$

$$258*7 + 180*(-10) + 0 =$$

$$258*7 + 180*(-10) + (M - M)=$$ (for any $$M$$)

$$258*7 + 180*(-10) + (k*6*30*43 - k*6*30*43)=$$ (for any integer $$k$$)

$$[258*7 + k*6*30*43] + [180*(-10) - k*6*30*43] =$$

$$[258*7+258*30k] + [-180*10 - 180*43k] =$$

$$258(7+30k) + 180(-10 - 43k)$$

So $$m = 7+30k$$ and $$n= -10 -43k$$ for any integer $$k$$ will be a solution so there are infinitely many solutions.

Including $$m = -23$$ and $$n=33$$

But $$m=7$$ and $$n=-10$$ are the "smallest" solution (where $$|m-n|$$ is least)

• I don't understand why you promote the backward version when the forward version is generally much easier and less error prone (and here it is the approach the OP asks about). Get on the bandwagon! Commented Nov 7, 2019 at 18:35
• I'm not promoting. I'm just describing what the answer is and how you can derive a method of doing on your own if you don't know a method. Commented Nov 7, 2019 at 21:26

You started out correctly applying the forward extended Euclidean algorithm but went astray at the 4th line by not using the (positive) remainder. Instead, it should proceed from there as

\begin{align} r_4 = 24\, &= \ \ {-}2(258)\ +\ 3(180)\ \ \,[=\, r_2 - 2\, r_3]\\[.2em] {\rm Bezout\ Identity}\ \rightarrow\ r_5\, =\ 6\, &= \ \ \ \ \ 7 (258) -10 (180)\ \ \,[=\, r_3 - 3\, r_4] \\[.2em] r_6\, =\ 0\, &= -30(258)+43(180)\ \ \,[=\, r_4 - 4\, r_5] \end{align}\qquad\qquad\qquad\qquad

Remark  You could get back on track by adding your final two equations, but it is usually more efficient to choose $$\,q_i\,$$ to obtain the least (positive) value $$\, r_{i+1} = r_{i-1} - q_i r_i,\,$$ which occurs when $$\,q_i$$ is the quotient $$r_{i-1}\div r_i,\,$$ so $$\,r_{i+1} = r_{i-1}\bmod r_i\,$$ as in the Euclidean algorithm. Any value of $$\,q_i\,$$ will preserve the gcd since $$\,(r_i,r_{i+1}) = (r_i,\, r_{i-1} - q_i r_i)= (r_i,r_{i-1})\,$$ but the goal is to generate a minimal decreasing (remainder) sequence $$\,r_i\,$$ in order to optimize the search for the gcd (= least positive linear combination of gcd arguments). In fact generally we can eliminate half of the computations by using least magnitude (signed) remainders, e.g. here.

$$258=180+78$$

$$180=2\times78+24$$

$$78=3\times24+6$$

$$24=4\times6$$

Therefore,

$$78-3\times24=6$$

$$78-3\times(180-2\times78)=6$$

$$7\times78-3\times180=6$$

$$7\times(258-180)-3\times180=6$$

$$7\times258-10\times180=6$$

• Please see my comment on fleablood's answer. Commented Nov 7, 2019 at 18:36