  We extend the necessity part of Lucas Lehmer iteration for testing Mersenne
prime to all base and uniformly for both generalized Mersenne and Wagstaff
numbers(the later correspond to negative base). The role of the quadratic
iteration $x \rightarrow x^2-2$ is extended by Chebyshev polynomial $T_n(x)$
with an implied iteration algorithm because of the compositional identity
$T_n(T_m(x))=T_{nm}(x)$. This results from a Chebyshev polynomial primality
test based essentially on the Lucas pair $(\omega_a,\overline{\omega}_a)$,
$\omega_a=a+\sqrt{a^2-1}$, where $a \neq 0 \pm 1$. It seems interesting that
the arithmetic are all coded in the Chebyshev polynomials $T_n(x)$.
