Coprime polynomials over finite fields have interesting applications in coding theory and cryptography. While counting and enumeration questions have been settled for generic pairs of coprime polynomials, the case where some of the coefficients are constrained is more complicated and not completely addressed in the literature yet. Motivated by a cryptographic application, in this talk we focus on counting coprime pairs where both polynomials have a nonzero constant term. We first show how this problem can be settled using a recurrence equation approach. Then, we introduce a different perspective based on Euclid’s algorithm, unveiling interesting connections with formal languages and combinatorics. In doing so, we derive again the same counting formula for polynomials over the binary field $GF(2)$, and devise an enumeration algorithm.