0
$\begingroup$

I'm taking an "Algebra for Computer Science" course, and the professor briefly touched upon an implementation of the Extended Euclidean algorithm I can't seem to understand right now.

In previous algebra courses I learnt the following:

  • Use the euclidean algorithm
  • Convert each equation from the form $a = qb + r$ to $r = a - qb$
  • Starting from the final equation, of the form: $\gcd(a, b) = a - qb$, substitute $b$ with the previous remainder, then distribute and sum, then repeat. The procedure ends once the form described in Bézout's identity is reached. $$\gcd(a, b) = ... = ua + vb$$

The new lecture notes instead describe a constructive process, based on the following property:

$$ au + bv = m \implies m = (qb + r)u + bv = ru + b(v+qu) $$

We then write a step of Euclid's algorithm as follows:

$$ \gcd(a = qb + r, b \mid u, v) \to \gcd(r, b \mid u, v + qu) \to \gcd (b, r \mid v + qu, u) $$

Until we get to $\gcd (m, 0 \mid l_1(u, v), l_2 (u, v))$ and solve the linear system:

$$ \begin{cases} l_1(u, v) = 1 \\ l_2(u, v) = 0 \end{cases} $$

What I don't understand is the connection between these two methods (or really the intuition of why this second method works), and why this second method should be "easier" (for humans, at least; I do get that recursively constructing a $2\times 2$ matrix and solving a tiny linear system is very simple for a computer, but the professor claimed this method is simply "easier").

$\endgroup$
5
  • $\begingroup$ What do the notation | stand for? I know $\gcd(x,y)$ but have no clue to guess what's $\gcd(x,y\color{red}{|}z)$ means. $\endgroup$ Commented Feb 3, 2023 at 16:22
  • $\begingroup$ It's "the gcd of $a$ and $b$, calculated while keeping track of the evolution of $u$ and $v$"; It's like in linear algebra, when you keep track of some parameter (e.g. when solving a linear system or when taking matrix inverses) and you add a $|$ to your matrix to separate the actual matrix from the thing you're keeping track of. $\endgroup$ Commented Feb 3, 2023 at 16:37
  • $\begingroup$ I'm rather computer-sciences uneducated but I wonder if your second algorithm is not the so-called “Blankinship algorithm”? $\endgroup$ Commented Feb 3, 2023 at 16:58
  • $\begingroup$ From a cs point of view the second algorithm is better because it's tail recursive. In my opinion that makes it less error prone for humans. The wikipedia page might help: en.wikipedia.org/wiki/Extended_Euclidean_algorithm $\endgroup$ Commented Feb 3, 2023 at 17:37
  • $\begingroup$ @jpboucheron Yes!, it looks like this is what I'm looking for. I'm getting a very similar system, and it's easier to perform simple row operations than it is to keep track of the evolution of $u$ and $v$ explicitly $\endgroup$ Commented Feb 3, 2023 at 19:45

2 Answers 2

Reset to default
0
$\begingroup$

We want to find the g.c.d. of two nonzero integers $a,b$ and we suppose that $b\geqslant1$. Let's define a finite sequence $(u_k)_k$ by induction as follows: $u_0=a$, $u_1=b$, and $\bbox[silver,8px]{\forall k\geqslant1\quad u_{k+1}=u_{k-1}-q_ku_k}$, where $q_k$ is the (integer!) quotient in the euclidian division of $u_{k-1}$ by $u_k$.

These are the coefficients of the usual euclidian algorithm. $$\left\{\begin{array}{rcl} \overset{\scriptscriptstyle a}{u_0}&=&q_1\overset{\scriptscriptstyle b}{u_1}+u_2,\\ u_1&=&q_2u_2+u_3,\\ &\vdots&\\ u_{n-1}&=&q_nu_n+\underset{\scriptscriptstyle\gcd(a,b)}{u_{n+1}}, \end{array}\right.$$ where $n+1$ is the first integer $h$ for which $u_h\neq0$, which implies that $u_{n+1}=\gcd(a,b)$.

Also let's define: $M_k=\begin{pmatrix}0&1\\1&-q_k\end{pmatrix},\ k\geqslant1$.

Now we easily check that $\begin{pmatrix}u_k\\u_{k+1}\end{pmatrix} =M_k\begin{pmatrix}u_{k-1}\\u_k\end{pmatrix} =\underbrace{M_kM_{k-1}\ldots M_1}_{P_k}\begin{pmatrix}u_0\\u_1\end{pmatrix}$.

In particular, putting $P_n=\begin{pmatrix}\alpha&\beta\\ \gamma&\delta\end{pmatrix}$, we have $\begin{pmatrix}u_n\\u_{n+1}\end{pmatrix} =P_n\begin{pmatrix}u_0\\u_1\end{pmatrix}$ and finally obtain $\gcd(a,b)=u_{n+1}=\gamma u_0+\delta u_1=\gamma a+\delta b$, which is the desired Bézout relation.

Hence if we write a program along these lines, the only things we have to calculate at step $k\geqslant1$ are $u_{k+1}$, the four coefficients of $P_k=M_kP_{k-1}$, and we can forget about the former values.

Example with $(a,b)=(29,17)$. $$\left\{\begin{array}{rcll} 29&=&1\times17+12,&\quad P_1=M_1=\left(\begin{smallmatrix}0&1\\1&-1\end{smallmatrix}\right)\\[4pt] 17&=&1\times12+5,&\quad P_2=\left(\begin{smallmatrix}1&-1\\-1&2\end{smallmatrix}\right)\\[4pt] 12&=&2\times5+2,&\quad P_3=\left(\begin{smallmatrix}-1&2\\3&5\end{smallmatrix}\right)\\[4pt] 5&=&2\times2+1,&\quad P_4=\left(\begin{smallmatrix}3&-5\\ \color{red}{-7}&\color{red}{12}\end{smallmatrix}\right). \end{array}\right.$$ Conclusion: $1=\gcd(29,17)=-7\times29+12\times17$.

$\endgroup$
0
$\begingroup$

I like to write the extended algorithm with continued fractions. If you concentrate on just the fractions in the "tableau," each pair of consecutive fractions (these are called convergents) has a crossed product $\pm 1,$ such as $ 3 \cdot 4 - 11 \cdot 1 = 1$ and then $11 \cdot 9 - 25 \cdot 4 = -1$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ \begin{array}{cccccccccccccc} \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 3 }{ 1 } & & \frac{ 11 }{ 4 } & & \frac{ 25 }{ 9 } & & \frac{ 61 }{ 22 } & & \frac{ 147 }{ 53 } \end{array} $$ $$ $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$ $$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ \gcd( 147, 53 ) = ??? $$

$$ \frac{ 147 }{ 53 } = 2 + \frac{ 41 }{ 53 } $$ $$ \frac{ 53 }{ 41 } = 1 + \frac{ 12 }{ 41 } $$ $$ \frac{ 41 }{ 12 } = 3 + \frac{ 5 }{ 12 } $$ $$ \frac{ 12 }{ 5 } = 2 + \frac{ 2 }{ 5 } $$ $$ \frac{ 5 }{ 2 } = 2 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccc} & & 2 & & 1 & & 3 & & 2 & & 2 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 3 }{ 1 } & & \frac{ 11 }{ 4 } & & \frac{ 25 }{ 9 } & & \frac{ 61 }{ 22 } & & \frac{ 147 }{ 53 } \end{array} $$ $$ $$ $$ 147 \cdot 22 - 53 \cdot 61 = 1 $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$\endgroup$

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.