Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$a = 123,\ b = 321.$$ The first part of the question I'm trying to solve wants me to find $d = \gcd(a,b)$. I can quickly solve this by using the Euclidean algorithm, and $d$ is $3$.

However, the second part requires me to express $d$ as an integer combination $ra + sb$, for some integers $r$ and $s$.

Is there any way to do this other than mashing some multiples of $a$ and $b$ on a calculator and praying the difference comes out as $|3|$?

share|improve this question
    
See the extended Euclidean Algorithm. –  Bill Dubuque Aug 11 '12 at 22:11
add comment

3 Answers

up vote 6 down vote accepted

The answer is YES, using the Euclidean algorithm backwards.

For $b=321$ and $a=123$, the Euclidean algorithm yields:

  1. $b=2\cdot a+75$
  2. $a=1\cdot75+48$
  3. $75=1\cdot48+27$
  4. $48=1\cdot27+21$
  5. $27=1\cdot21+6$
  6. $21=3\cdot6+3$ and $3$ divides $6$

Hence the greatest common divisor of $a$ and $b$ is $d=3$. Furthermore:

  • $d=21-3\cdot6$ by (6)
  • $6=27-21$ by (5), hence $d=21-3\cdot(27-21)=4\cdot21-3\cdot27$
  • $21=48-27$ by (4), hence $d=4\cdot(48-27)-3\cdot27=4\cdot48-7\cdot27$
  • $27=75-48$ by (3), hence $d=4\cdot48-7\cdot(75-48)=11\cdot48-7\cdot75$
  • $48=a-75$ by (2), hence $d=11\cdot(a-75)-7\cdot75=11\cdot a-18\cdot75$
  • $75=b-2\cdot a$ by (1), hence $d=11\cdot a-18\cdot(b-2a)=47\cdot a-18\cdot b$

Finally, $d=47a-18b$.

share|improve this answer
add comment

The idea is to go backward using the Euclidean Algorithm.

Since $321$ and $123$ has a long Euclidean algorithm, I will do $23$ and $7$ instead to illustrate:

$23 = 3(7) + 2 \ \ \ (1)$

$7 = 3(2) + 1 \ \ \ (2)$

$2 = 2(1) + 0$

So gcd(23, 7) = 1.

Now by equation (2)

$1 = 7 - 3(2) \ \ \ (*)$

By equation (1), you have

$2 = 23 - 3(7)$

Substituting into $(*)$, you get

$1 = 7 - 3(23 - 3(7)) = 7 - 3(23) + 9(7) = 10(7) - 3(23)$

So you have

$gcd(23,7) = 1 = 10(7) - 3(23)$.

share|improve this answer
    
It's useful to know that this procedure is called the Extended Euclidean algorithm and requires no thought. –  Kris Aug 11 '12 at 21:38
    
@achacttn and requires no "praying". –  William Aug 11 '12 at 21:42
add comment

The matrix Euclidean algorithm is reasonably useful to know, and reasonably easy to execute. The idea is to write down the remainders as a row vector on the right hand side of the equality. The left hand side will be a vector-matrix multiplication. To get the next line, on the right hand side we need to shift the right column one to the left, and then the new right column is a linear combination of the old columns. For instance 75 is one copy of 321 minus two copies of 123. The left hand side is done the same: the left column scoots over one to the left, and the right column is a linear combination. For instance $\begin{smallmatrix}1\\-2\end{smallmatrix}$ is one copy of the left column $\begin{smallmatrix}1\\0\end{smallmatrix}$ minus two copies of the right column $\begin{smallmatrix}0\\1\end{smallmatrix}$, abbreviated as $N=L-(2)(R)$.

So in each equation below, we figure out how to fix the right hand side using the division algorithm, then we just do the same thing to the left hand side.

$$\newcommand{\matty}[6]{ \begin{bmatrix} 321 & 123 \end{bmatrix} \cdot \begin{bmatrix} #1 & #3 \\ #2 & #4 \end{bmatrix} = \begin{bmatrix} #5 & #6 \end{bmatrix}} \matty{1}{0}{0}{1}{321}{123} \phantom{ \qquad N = L - (2)(R) }\\ \matty{0}{1}{1}{-2}{123}{75} \qquad N = L - (2)(R) \\ \matty{1}{-2}{-1}{3}{75}{48} \qquad N = L - (1)(R)\\ \matty{-1}{3}{2}{-5}{48}{27} \qquad N = L - (1)(R)\\ \matty{2}{-5}{-3}{8}{27}{21} \qquad N = L - (1)(R)\\ \matty{-3}{8}{5}{-13}{21}{ 6} \qquad N = L - (1)(R)\\ \matty{5}{-13}{-18}{47}{ 6}{ 3} \qquad N = L - (3)(R)\\ \matty{-18}{47}{41}{-107}{ 3}{ 0} \qquad N = L - (2)(R)\\ $$

This gives us the information that $$3 = (321)(-18) + (123)(47)$$ but even more, it tells us that $$0 = (321)(41) + (123)(-107)$$ so we can actually find lots of ways to get $3$:

$$3 = (321)(-18+41k) + (123)(47-107k) \text{ for any } k$$

so for instance we also get ($k=1$):

$$3 = (321)(23) + (123)(-60)$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.