Euclid meets Popeye: The Euclidean Algorithm for $2\times 2$ matrices

Abstract

An analogue of the Euclidean algorithm for square matrices of size 2 with integral non-negative entries and strictly positive determinant $n$ defines a finite set $\mathcal{R}(n)$ of Euclid-reduced matrices corresponding to elements of $\{(a,b,c,d)\in {\mathbb{N}}^4|n=ab-cd,0\le c,d<a,b\}$. With Popeye's help[2] on the use of sails of lattices we show that $\mathcal{R}(n)$ contains $\sum d|n,d^2\ge n(d+1-n/d)$ elements.