  We examine two particular constructions of Costas arrays known as the Taylor
variant of the Lempel construction, or the $T_{4}$ construction, and the
variant of the Golomb construction, or the $G_{4}$ construction. We connect
these constructions with the concept of Fibonacci primitive roots, and show
that under the Extended Riemann Hypothesis the $T_{4}$ and $G_{4}$
constructions are valid infinitely often.
