  There has been interest during the last decade in properties of the sequence
{gcd(a^n-1,b^n-1)}, n=1,2,3,..., where a,b are fixed (multiplicatively
independent) elements in either the rational integers, the polynomials in one
variable over the complex numbers, or the polynomials in one variable over a
finite field. In the case of the rational integers, Bugeaud, Corvaja and
Zannier have obtained an upper bound exp(\epsilon n) for any given \epsilon >0
and all large n, and demonstrate its approximate sharpness by extracting from a
paper of Adleman, Pomerance, and Rumely a lower bound \exp(\exp(c\frac{log
n}{loglog n})) for infinitely many n, where c is an absolute constant. The
upper bound generalizes immediately to gcd(\Phi_N(a^n), \Phi_N(b^n)) for any
positive integer N, where \Phi_N(x)$ is the Nth cyclotomic polynomial, the
preceding being the case N=1. The lower bound has been generalized in the first
author's Ph.D. thesis to N=2. In this paper we generalize the lower bound for
arbitrary N but under GRH (the generalized Riemann Hypothesis). The analogue of
the lower bound result for gcd(a^n-1,b^n-1) over F_q[T] was proved by
Silverman; we prove a corresponding generalization (without GRH).
