Find integers $u$ and $v$ satisfying $20u+63v=1$

Question

Find integers $u$ and $v$ satisfying $20u+63v=1$.

I tried to use the Euclidean Algorithm $63=20.3+3$, $20=3.6+2$, $3=2.1+1$ Then we have $1=3-2.$ Now what should be the coefficients?

Answer 1

This is how I do it.

\begin{array}{r|rrr} a & b & c & d \\ \hline & 63 & 1 & 0 \\ -3 & 20 & 0 & 1 \\ \hline -7 & 3 & 1 & -3 \\ & -1 & -7 & 22 \\ \hline & 1 & 7 & -22 \end{array}

Note that, in each row, $b = 63c + 20d$. The "next" row is computed by multiplying the "current" $(b,c,d)$ by $a$ and adding the result to the previous $(b,c,d)$.

Hence $1 = 63(7) + 20(-22)$

Answer 2

We can use the extended Euclidean algorithm to find the coefficients.

As you observed, the Euclidean algorithm yields \begin{align*} 63 & = 3 \cdot 20 + 3\\ 20 & = 6 \cdot 3 + 2\\ 3 & = 1 \cdot 2 + 1\\ 2 & = 2 \cdot 1 + 0 \end{align*} Working backwards, we obtain \begin{align*} 1 & = 3 - 2\\ & = 3 - (20 - 6 \cdot 3)\\ & = 7 \cdot 3 - 20\\ & = 7(63 - 3 \cdot 20) - 20\\ & = 7 \cdot 63 - 22 \cdot 20 \end{align*} so a particular solution of the equation $20u + 63v = 1$ is $u = -22$ and $v = 7$. The general solution of a linear Diophantine equation $ax + by = c$ with particular solution $x_0, y_0$ is \begin{align*} x & = x_0 + \frac{b}{d}t\\ y & = y_0 - \frac{a}{d}t \end{align*} where $d = \gcd(a, b)$ and $t \in \mathbb{Z}$. Here $a = 20$, $b = 63$, $d = \gcd(20, 63) = 1$, $u_0 = -22$, and $v_0 = 7$, so we obtain the general solution \begin{align*} u & = -22 + 63t\\ v & = 7 - 20t \end{align*} where $t \in \mathbb{Z}$, as you can verify by direct calculation.

Answer 3

A (not really) alternative approach. We construct the continued fraction of $\frac{63}{20}$:

$$ \frac{63}{20}=\left[3;\frac{20}{3}\right]=\left[3;6,\frac{3}{2}\right]=\left[3;6,1,2\right]\tag{1} $$ then we truncate it and we expand it back: $$ [3;6,1] = [3;7] = \frac{22}{7}. \tag{2} $$ By the properties of continued fractions, $\frac{63}{20}-\frac{22}{7}$ is a number of the form $\pm\frac{1}{7\cdot 20}$. Indeed $$ 63\cdot 7 - 20\cdot 22 = 1 \tag{3} $$ and we have found a solution of the original problem, hence all of them: $$ u=-22+63k,\quad v=7-63k.\tag{4} $$