Exercise 1652Number theory › Divisibility and gcdL1Added 3 Nov 2026

GCD via the Euclidean matrix

#gcd#Euclidean algorithm#matrix

Statement

Show that the Euclidean algorithm applied to $(a,b)$ can be written as a sequence of matrix multiplications with matrices in $SL_2(\mathbb{Z})$ , and deduce that the gcd is preserved.

Hint

Each step $(a,b)\mapsto(b,a-qb)$ is left multiplication by $\begin{pmatrix}0&1\\1&-q\end{pmatrix}$ , which has determinant $-1$ .

Show solutionHide solution

Solution

Step. If $a=qb+r$ , the transformation $(a,b)\mapsto(b,r)$ is $\begin{pmatrix}0&1\\1&-q\end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix}=\begin{pmatrix}b\\a-qb\end{pmatrix}$ .

Determinant. $\det\begin{pmatrix}0&1\\1&-q\end{pmatrix}=-1$ , so this matrix is in $GL_2(\mathbb{Z})$ with inverse $\begin{pmatrix}q&1\\1&0\end{pmatrix}$ .

GCD preservation. The map $(a,b)\mapsto(b,a-qb)$ preserves $\gcd$ because the two components generate the same ideal in $\mathbb{Z}$ .

Conclusion. The Euclidean algorithm is a sequence of elementary transformations in $GL_2(\mathbb{Z})$ , and the gcd is preserved.

GCD via the Euclidean matrix

Statement

Solution

More problems in Divisibility and gcd