Exercise 1.2.2 (Linear equation)

Question

Find the greatest common divisor $g$ of the numbers 1819 and 3587, and then find integers $x$ and $y$ to satisfy $$1819x + 3587y = g$$

Issa Rice · Accepted Answer

There's a few ways to do this problem.
One way is the following: whenever we write the remainder in Euclid's algorithm, we always make sure to express that remainder as an integer linear combination of the original two numbers.
The rightmost column below does this bookkeeping work, while the two columns on the left are the inputs to the gcd function at each stage.
\begin{center}
\begin{tabular}{ r|r|l }
 3587 & 1819 & $1768 = 3587 - 1819$ \ 
 1819 & 1768 & $\begin{aligned}[t]
     51 &= 1819 - 1768 \
        &= 1819 - (3587 - 1819) \
        &= 2\cdot 1819 - 3587
 \end{aligned}$  \ 
 1768 & 51 & $\begin{aligned}[t]
     34 &= 1768 - 34\cdot 51 \
        &= (3587 - 1819) - 34\cdot (2\cdot 1819 - 3587) \
        &= 3587 - 1819 - 68\cdot 1819 + 34\cdot 3587 \
        &= 35\cdot 3587 - 69\cdot 1819
 \end{aligned}$ \
 51 & 34 & $\begin{aligned}[t]
     17 &= 51 - 34 \
        &= (2\cdot 1819 - 3587) - (35\cdot 3587 - 69\cdot 1819) \
        &= 2\cdot 1819 - 3587 - 35\cdot 3587 + 69\cdot 1819 \
     17 &= 71 \cdot 1819 - 36 \cdot 3587
 \end{aligned}$ \
\end{tabular}
\end{center}
Thus $g = 17, x=71, y=-36$.

Exercise 1.2.2 (Linear equation)

Answers

Comments

3587	1819	$1768 = 3587 - 1819$
1819	1768	$\begin{aligned} 51 & = 1819 - 1768 \\ = 1819 - (3587 - 1819) \\ = 2 \cdot 1819 - 3587 \end{aligned}$
1768	51	$\begin{aligned} 34 & = 1768 - 34 \cdot 51 \\ = (3587 - 1819) - 34 \cdot (2 \cdot 1819 - 3587) \\ = 3587 - 1819 - 68 \cdot 1819 + 34 \cdot 3587 \\ = 35 \cdot 3587 - 69 \cdot 1819 \end{aligned}$
51	34	$\begin{aligned} 17 & = 51 - 34 \\ = (2 \cdot 1819 - 3587) - (35 \cdot 3587 - 69 \cdot 1819) \\ = 2 \cdot 1819 - 3587 - 35 \cdot 3587 + 69 \cdot 1819 \\ 17 & = 71 \cdot 1819 - 36 \cdot 3587 \end{aligned}$

Exercise 1.2.2 (Linear equation)

Answers

Comments

Add answer