  We address the enumeration of coprime polynomial pairs over $\F_2$ where both
polynomials have a nonzero constant term, motivated by the construction of
orthogonal Latin squares via cellular automata. To this end, we leverage on
Benjamin and Bennett's bijection between coprime and non-coprime pairs, which
is based on the sequences of quotients visited by dilcuE's algorithm (i.e.
Euclid's algorithm ran backward). This allows us to break our analysis of the
quotients in three parts, namely the enumeration and count of: (1) sequences of
constant terms, (2) sequences of degrees, and (3) sequences of intermediate
terms. For (1), we show that the sequences of constant terms form a regular
language, and use classic results from algebraic language theory to count them.
Concerning (2), we remark that the sequences of degrees correspond to
compositions of natural numbers, which have a simple combinatorial description.
Finally, we show that for (3) the intermediate terms can be freely chosen.
Putting these three obeservations together, we devise a combinatorial algorithm
to enumerate all such coprime pairs of a given degree, and present an
alternative derivation of their counting formula.
