---
abstract: 'It is known that the greatest common divisor of two Fibonacci numbers is again a Fibonacci number. It is called the *strong divisibility property*. However, this property does not hold for every second order sequence. In this paper we study the generalized Fibonacci polynomials and classify them in two types depending on their Binet formula. We give a complete characterization for those polynomials that satisfy the strong divisibility property. We also give formulas to calculate the $\gcd$ of those polynomials that do not satisfy the strong divisibility property.'
---

Rigoberto Flórez\
Department of Mathematics and Computer Science\
The Citadel\
Charleston, SC\
U.S.A.\
[rigo.florez@citadel.edu]{}\
 \
Robinson A. Higuita\
Instituto de Matemáticas\
Universidad de Antioquia\
Medellín\
Colombia\
[robinson.higuita@udea.edu.co]{}\
 \
Antara Mukherjee\
Department of Mathematics and Computer Science\
The Citadel\
Charleston, SC\
U.S.A.\
[antara.mukherjee@citadel.edu]{}

.2 in

Introduction
============

It is well known that the greatest common divisor ($\gcd$) of two Fibonacci numbers is a Fibonacci number [@koshy]. Thus, $\gcd(F_m,F_n)=F_{\gcd(m,n)}$. It is called the *strong divisibility property* or *Fibonacci gcd property*. In this paper we study divisibility properties of generalized Fibonacci polynomials (GFP) and in particular we give characterization of the strong divisibility property for these polynomials.

We classify the GFP in two types, the Lucas type and the Fibonacci type, depending on their closed formulas or their Binet formulas (see for example, $L_n(x)$ (\[bineformulados\]) and $R_n(x)$ (\[bineformulauno\]), and the Table \[equivalent\]). That is, if after solving the characteristic polynomial of the GFP we obtain a closed formula that look like the Binet formula for Fibonacci (Lucas) numbers, it is called Fibonacci (Lucas) type polynomials. Familiar examples of Fibonacci type polynomials are: Fibonacci polynomials, Pell polynomials, Fermat polynomials, Chebyshev polynomials of second kind, Jacobsthal polynomials and one type of Morgan-Voyce polynomials. Examples of Lucas type polynomials are: Lucas polynomials, Pell-Lucas polynomials, Fermat-Lucas polynomials, Chebyshev polynomials of first kind, Jacobsthal-Lucas polynomials and second type of Morgan-Voyce polynomials.

In Theorem \[gcd:property:fibonacci\] we prove that a GFP satisfies the strong divisibility property if and only if it is of Fibonacci type. The Theorem \[second:main:thm\] shows that the Lucas type polynomials satisfy the strong divisibility property partially and also gives the $gcd$ for those cases in which the property is not satisfied.

A Lucas type polynomial is equivalent to a Fibonacci type polynomial if they both have the same recurrence relation but different initial conditions (see also Flórez et al. [@florezHiguitaMuk]). The Theorem \[combine:gcd:Lucas:Fibobacci\] proves that two equivalent GFP satisfies the strong divisibility property partially and gives the $gcd$ for those cases in which the property is not satisfied.

In 1969 Webb and Parberry [@Webb] extended the strong divisibility property to the Fibonacci Polynomials. In 1974 Hoggatt and Long [@HoggattLong] proved the strong divisibility property for one type of generalized Fibonacci polynomial. In 1978 Hoggatt and Bicknell-Johnson [@hoggatt] extended the result mentioned in [@HoggattLong] to some cases of Fibonacci type polynomials. However, they did not prove the necessary and sufficient condition and their paper does not cover the Lucas type case. In 2005 Rayes, Trevisan, and Wang [@Rayes] proved that the strong divisibility property holds partially for the Chebyshev polynomials (we prove the general result in Theorem \[second:main:thm\]). Over the years several other authors have been also interested in the divisibility properties of sequences, some papers are [@hall; @kimberling; @kimberlingStrong1; @kimberlingStrong2; @lucas; @mcdaniel; @norfleet; @ward].

Lucas [@lucas] proved the strong divisibility property (SDP) for Fibonacci numbers. However, the study of SDP for Lucas numbers took until 1991, when McDaniel [@mcdaniel] provided proofs that the Lucas numbers satisfy the SDP partially. In 1995 Hilton et al. [@hilton] gave some more precise results about this property. As mentioned above several authors have been interested in the divisibility properties for Fibonacci type polynomials. However, the Lucas type polynomials have been less studied. Here we complete three cases of the SDP. Indeed, we give a characterization for the SDP for Fibonacci type polynomials and study both the SDP for Lucas type polynomials and the SDP for the combinations of Lucas type polynomials and Fibonacci type polynomials. Finally we provide an open question for the most general case of combination of two polynomials.

Generalized Fibonacci polynomials GFP {#General:Fibonacci:Polynomial}
=====================================

In the literature there are several definitions of generalized Fibonacci polynomials. However, the definition that we introduce here is simpler and covers other definitions. The background given in this section is a summary of the background given in [@florezHiguitaMuk]. However, the definition of generalized Fibonacci polynomial here is not exactly the same as in [@florezHiguitaMuk]. The *generalized Fibonacci polynomial* sequence, denoted by GFP, is defined by the recurrence relation

$$\label{Fibonacci;general}
G_0(x)=p_0(x), \; G_1(x)= p_1(x),\;  \text{and} \;  G_{n}(x)= d(x) G_{n - 1}(x) + g(x) G_{n - 2}(x) \text{ for } n\ge 2$$

where $p_0(x)$ is a constant and $p_1(x)$, $d(x)$ and $g(x)$ are non-zero polynomials in $\mathbb{Z}[x]$ with $\gcd(d(x), g(x))=1$.

For example, if we let $p_0(x)=0$, $p_1(x)=1$, $d(x)=x$, and $g(x)=1$ we obtain the regular Fibonacci polynomial sequence. Thus, $$F_0(x)= 0, \; F_1(x)= 1, \; \text{and} \;  F_{n}(x)= x F_{n - 1}(x) + F_{n - 2}(x) \text{ for } n\ge 2.$$

Letting $x=1$ and choosing the correct values for $p_0(x)$, $p_1(x)$, $d(x)$ and $g(x)$, the generalized Fibonacci polynomial sequence gives rise to three classical numerical sequences, the Fibonacci sequence, the Lucas sequence and the generalized Fibonacci sequence.

In Table \[familiarfibonacci\] there are more familiar examples of GFP (see [@florezHiguitaMuk; @Pell; @Fermat; @koshy]). Hoggatt and Bicknell-Johnson [@hoggatt] show that Schechter polynomials are another example of generalized Fibonacci polynomials.

\[!ht\]

Fibonacci type and Lucas type polynomials
-----------------------------------------

If we impose some conditions on the Definition (\[Fibonacci;general\]) we obtain two type of distinguishable polynomials. We say that a sequences as in (\[Fibonacci;general\]) is *Lucas type* or *first type* if $2p_{1}(x)=p_{0}(x)d(x)$ with $p_{0}\ne 0$. We say that a sequences as in (\[Fibonacci;general\]) is *Fibonacci type* or *second type* if $p_{0}(x)=0$ with $p_{1}(x)$ a constant.

If $d^2(x)+4g(x)> 0$, then the explicit formula for the recurrence relation (\[Fibonacci;general\]) is given by

$$\label{solutionrecurrencerelationuno}
 G_{n}(x) = t_1 a^{n} + t_2 b^{n}$$

where $a(x)$ and $b(x)$ are the solutions of the quadratic equation associated to the second order recurrence relation $G_{n}(x)$. That is, $a(x)$ and $b(x)$ are the solutions of $z^2-d(x)z-g(x)=0$. The explicit formula for $G_{n}(x)$ given in (\[solutionrecurrencerelationuno\]) with $G_{0}(x)=p_{0}(x)$ and $G_{1}(x)=p_{1}(x)$ imply that $$\label{solutionrecurrencerelationdos}
 t_{1}=\dfrac{p_{1}(x)-p_{0}(x)b(x)}{a(x)-b(x)} \text{ and } t_{2}=\dfrac{-p_{1}(x)+p_{0}(x)a(x)}{a(x)-b(x)}$$

Using (\[solutionrecurrencerelationuno\]) and (\[solutionrecurrencerelationdos\]) we obtain the Binet formulas for the Generalized Fibonacci sequences of the Lucas type and Fibonacci type. Thus, substituting $2p_{1}(x)=p_{0}(x)d(x)$ in (\[solutionrecurrencerelationdos\]) we obtain that $t_{1}=t_{2}= p_{0}(x)/2$. Substituting this in (\[solutionrecurrencerelationuno\]) and letting $\alpha$ be $2/p_{0}(x)$ we obtain the Binet formula for Generalized Fibonacci sequence of *Lucas type* or *first type* $$\label{bineformulados}
L_n(x)=\frac{a^{n}(x)+b^{n}(x)}{\alpha}.$$ We want $\alpha$ be an integer, therefore $|p_{0}(x)|=1 \text { or } 2$.

Now, substituting $p_{0}(x)=0$ and the constant $p_{1}(x)$ in (\[solutionrecurrencerelationdos\]) we obtain that $t_{1}=t_{2}=p_{1}(x)$. Substituting this in (\[solutionrecurrencerelationuno\]) we obtain the Binet formula for Generalized Fibonacci sequence of *Fibonacci type* or *second type* $$\label{bineformulaunogeneral}
R_n(x)=\frac{p_{1}(x)\left(a^{n}(x)-b^{n}(x)\right)}{a(x)-b(x)}.$$ In this paper we are interested only on $R_n(x)$ when $p_1(x)=1$. Therefore, the Binet formula $R_n(x)$ that we use here is $$\label{bineformulauno}
R_n(x)=\frac{a^{n}(x)-b^{n}(x)}{a(x)-b(x)}.$$

Note that $a(x)+b(x)=d(x)$, $a(x)b(x)= -g(x)$ and $a(x)-b(x)=\sqrt{d^2(x)+4g(x)}$ where $d(x)$ and $g(x)$ are the polynomials defined on the generalized Fibonacci polynomials.

A generalized Fibonacci polynomial which satisfies the Binet formula (\[bineformulados\]) is said to be of *first type* or *Lucas type* and it is of *Second type* or *Fibonacci type* if it satisfies the Binet formula (\[bineformulauno\]). Horadam [@horadam-synthesis] and André-Jeannin [@Richard] have studied these polynomials in detail.

The sequence of polynomials that have Binet representations $R_n(x)$ or $L_n(x)$ depend only on $d(x)$ and $g(x)$ defined on the generalized Fibonacci polynomials. We say that a generalized Fibonacci sequence of Lucas (Fibonacci) type is *equivalent* to a sequence of the Fibonacci (Lucas) type, if their recursive sequences are determined by the same polynomials $d(x)$ and $g(x)$. Notice that two equivalent polynomials have the same $a(x)$ and $b(x)$ in their Binet representations.

For example, the Lucas polynomial is a GFP of Lucas type, whereas the Fibonacci polynomial is a GFP of Fibonacci type. Lucas and Fibonacci polynomials are equivalent because $d(x)=x$ and $g(x)=1$ (see Table \[familiarfibonacci\]). Note that in their Binet representations they both have $a(x)= (x+\sqrt{x^2+4})/2$ and $b(x)=(x-\sqrt{x^2+4})/2$. The Table \[equivalent\] is based on information from the following papers [@Richard; @florezHiguitaMuk; @horadam-synthesis]. The leftmost polynomials in Table \[equivalent\] are of the Lucas type and their equivalent polynomials are in the third column on the same line. In the last two columns of Table \[equivalent\] we can see the $a(x)$ and $b(x)$ that the pairs of equivalent polynomials share. It is easy to obtain the characteristic equations of the sequences given in Table \[familiarfibonacci\], and the roots of the equations are $a(x)$ and $b(x)$.

For the sake of simplicity throughout this paper we use $a$ in place of $a(x)$ and $b$ in place of $b(x)$ when they appear in the Binet formulas. We use the notation $G_n^{*}$ or $G_n^{'}$ for $G_n$ depending on when it satisfies the Binet formulas (\[bineformulados\]) or (\[bineformulauno\]), respectively, (see Section \[mainresults:section\]).

For most of the proofs of GFP of Lucas type it is required that $\gcd(p_0(x), p_1(x))=1$, $\gcd(p_0(x), d(x))=1$ and $\gcd(d(x), g(x))=1$. It is easy to see that $\gcd(\alpha, G_{n}^{*}(x))=1$. Therefore, for the rest the paper we suppose that these four mentioned conditions hold for all generalized Fibonacci polynomial sequences of Lucas type treated here. We use $\rho$ to denote $\gcd(d(x),G_1(x))$. Notice that in the definition Pell-Lucas we have that $p_0(x)=2$ and $p_1(x)=2x$. Thus, the $\gcd(p_0(x),p_1(x))\ne 1$. Therefore, Pell-Lucas does not satisfy the extra conditions that were just imposed for Generalized Fibonacci polynomial. To solve this problem we define *Pell-Lucas-prime* as follows: $$Q_0^{\prime}(x)= 1, \; Q_1^{\prime}(x)= x, \; \text{and} \;  Q_{n}^{\prime}(x)= 2x Q_{n - 1}^{\prime}(x) + Q_{n - 2}^{\prime}(x) \text{ for } n\ge 2.$$ It easy to see that $2Q_{n}^{'}(x)=Q_{n}(x)$ and that $\alpha=2$. Flórez, Junes and Higuita [@florezHiguitaJunes] worked similar problems for numerical sequences.

**Note.** The definition of Generalized Fibonacci Polynomial in [@florezHiguitaMuk] differs with definition on this papers due to the initial conditions on the Fibonacci type polynomials. Thus, the initial conditions for the Fibonacci type polynomials in [@florezHiguitaMuk] is $G_{0}(x)=p_{0}(x)=1$ and so implicitly $G_{-1}(x)=0$. However, our definition for the Lucas type polynomials are the same in both papers.

\[!ht\]

Divisibility properties of Generalized Fibonacci Polynomials
============================================================

In this section we prove a few divisibility and $\gcd$ properties which are true for all GFP. These results will be used in a section later on to prove the main results of this paper.

Proposition \[prop2;1\] parts (1) and (2) is a generalization of Proposition 2.2 in [@florezjunes]. The proof here is similar the proof in [@florezjunes] since both use properties of integral domains. The reader can therefore update the proof in the afore-mentioned paper to obtain the proof of this proposition.

\[prop2;1\] Let $p(x), q(x), r(x),$ and $s(x)$ be polynomials.

(1) If $\gcd(p(x),q(x))=\gcd(r(x),s(x))=1$, then $$\gcd(p(x)q(x),r(x)s(x))=\gcd(p(x),r(x))\gcd(p(x),s(x))\gcd(q(x),r(x))\gcd(q(x),s(x)).$$

(2) If $\gcd(p(x),r(x))=1\gcd(q(x),s(x))=1$, then $$\gcd(p(x)q(x),r(x)s(x))=\gcd(p(x),s(x))\gcd(q(x),r(x)).$$

(3) If $z_1(x)=\gcd(p(x),r(x))$ and $z_2(x)=\gcd(q(x),s(x))$, then $$\gcd(p(x)q(x),r(x)s(x))=\frac{\gcd( z_2(x)p(x),z_1(x)s(x))\gcd( z_1(x)q(x), z_2(x)r(x))}{z_1(x)z_2(x)}.$$

We prove part (3). Since $\gcd(p(x),r(x))=z_1(x) $ and $\gcd(q(x),s(x))=z_2(x)$, there are polynomials $P(x)$, $S(x)$, $Q(x)$ and $R(x)$ with $\gcd(P(x),R(x))=\gcd(Q(x),S(x))=1$, such that $ p(x) = z_1(x)  P(x),\;   s(x)= z_2(x)  S(x),\;  r(x) = z_1(x)  R(x),   \;
q(x)= z_2(x)  Q(x)$. So, $$\begin{aligned}
\gcd(p(x)q(x),r(x)s(x)) &=&\gcd(z_1(x) P(x) z_2(x)Q(x), z_1(x) R(x) z_2(x)S(x))\\
&=&z_1(x)z_2(x)\gcd( P(x)Q(x), R(x)S(x)).\\\end{aligned}$$ From part (2) we know that $
\gcd( P(x)Q(x), R(x) S(x))=\gcd( P(x),S(x))\gcd( Q(x), R(x)).
$ Now it is easy to see that $$\gcd(p(x)q(x),r(x)s(x))=\frac{\gcd( z_2(x)p(x),z_1(x)s(x))\gcd( z_1(x)q(x), z_2(x)r(x))}{z_1(x)z_2(x)}.$$ This proves part (3).

We recall that $\rho=\gcd(d(x),G_1(x))$ and that for GFP of Lucas type it is required that $\gcd(p_0(x), p_1(x))=1$, $\gcd(p_0(x), d(x))=1$, $\gcd(p_0(x), g(x))=1$ and $\gcd(d(x), g(x))=1$. We also recall $p_0(x)=0$ and $p_1(x)=1$ for GFP of Fibonacci type.

For the rest of the paper we use the notation $G_n^{*}$ if the generalized Fibonacci polynomial $G_n$ satisfies the Binet formula (\[bineformulados\]) and $G_n^{'}$ if the generalized Fibonacci polynomial $G_n$ satisfies the Binet formula (\[bineformulauno\]). We use $G_n$ if the result does not need the mentioned classification to be true. We recall that for Lucas type polynomials $|p_{0}(x)| =1 \text{ or } 2$ and for Fibonacci type polynomial $p_{1}(x) =1$.

\[gcdlemmas\] If $\{ G_{n}(x)\}$ is a GFP of either Lucas or Fibonacci type, then

(1) $\gcd(d(x), G_{2n+1}(x))=G_1(x)$ for every positive integer $n$,

(2) If the GFP is of Lucas type, then $\gcd(d(x), G_{2n}^{*}(x))= 1$ and

    if the GFP is of Fibonacci type, then $\gcd(d(x), G_{2n}^{\prime}(x))= d(x)$

(3) $\gcd(g(x), G_n(x))=\gcd(g(x), G_{1}(x))=1,$ for every positive integer $n$.

We prove part (1) by induction, the proof of part (2) is similar and we omit it.

Let $\{G_n\}$ a GFP. Let $S(n)$ be the statement $$\rho=\gcd(d(x), G_{2n+1}(x))\text{  for  }n\ge 1.$$ To prove $S(1)$ we suppose that $\gcd(d(x), G_{3}(x))=r$. Thus, $r$ divides any linear combination of $d(x)$ and $G_3(x)$. Therefore, $r$ divides $G_3(x)-d(x) G_2(x)$. This and given that $G_3(x)= d(x) G_{2}(x) + g(x) G_{1}(x)$, imply that $r\mid g(x)G_{1}(x)$. So, $r\mid \gcd(d(x),g(x)G_{1}(x))$. Since $\gcd(d(x), g(x))=1$, we have that $r\mid \rho$. It is easy to see that $\rho \mid r$. Thus, $r=\gcd(d(x),G_1(x))$. This proves $S(1)$.

We suppose that $S(n)$ is true for $n=k-1$. That is, suppose that $\gcd(d(x), G_{2k-1}(x)) = \rho$. To prove $S(k)$ we suppose that $\gcd(d(x), G_{2k+1}(x))=r'$. Thus, $r'$ divides any linear combination of $d(x)$ and $G_{2k+1}(x)$. Therefore, $r'$ divides $G_{2k+1}(x)-d(x) G_{2k}(x)$. This and given that $G_{2k+1}(x)= d(x) G_{2k}(x) + g(x) G_{2k-1}(x)$, imply that $r'\mid g(x)G_{2k-1}(x)$. Therefore, $r'\mid \gcd(d(x),g(x)G_{2k-1}(x))$. Since $\gcd(d(x), g(x))=1$, we have that $r'\mid \gcd(d(x),G_{2k-1}(x))$. By the inductive hypothesis we know that $\gcd(d(x), G_{2k-1}(x)) = \rho$. Thus, $r'\mid \rho$. It is easy to see that $\gcd(d(x),G_{2k+1}(x))$ divides $r'$. So, $r'=\gcd(G_1(x), d(x))$.

We now show that depending on the type of the sequence it holds that $\gcd(d(x),G_1(x))=G_1$. If $\{G_n(x)\}$ is a GFP of Fibonacci type, by definition of $p(x)$ we that $G_1(x)=1$ (see comments after Binet formula ). Suppose that $\{G_n(x)\}$ is a GFP of Lucas type. Recall that $2p_{1}(x)=p_{0}(x)d(x)$ and that $|p_{0}(x)|=1 \text { or } 2$. The conclusion is straightforward since $G_1(x)=(a(x)+b(x))/\alpha=d(x)/\alpha$.

Proof of part (2). Let $S(n)$ be the statement $$\rho=\gcd(d(x), G_{2n}(x))\text{  for  }n\ge 1.$$ To prove $S(2)$ we suppose that $\gcd(d(x), G_{4}(x))=r$. Thus, $r$ divides any linear combination of $d(x)$ and $G_4(x)$. Therefore, $r$ divides $G_4(x)-d(x) G_3(x)$. This and given that $G_4(x)= d(x) G_{3}(x) + g(x) G_{2}(x)$, imply that $r\mid g(x)G_{2}(x)$. Therefore, $r\mid \gcd(d(x),g(x)G_{2}(x))$. Since $\gcd(d(x), g(x))=1$, we have that $r\mid \rho$. It is easy to see that $\rho \mid r$. Thus, $r=\gcd(d(x),G_2(x))$. This proves $S(2)$.

We suppose that $S(n)$ is true for $n=k-1$. That is, suppose that $\gcd(d(x), G_{2k-2}(x)) = \rho$. To prove $S(k)$ we suppose that $\gcd(d(x), G_{2k}(x))=r'$. Thus, $r'$ divides any linear combination of $d(x)$ and $G_{2k}(x)$. Therefore, $r'$ divides $G_{2k}(x)-d(x) G_{2k-1}(x)$. This and given that $G_{2k}(x)= d(x) G_{2k-1}(x) + g(x) G_{2k-2}(x)$, imply that $r'\mid g(x)G_{2k-2}(x)$. Therefore, $r'\mid \gcd(d(x),g(x)G_{2k-2}(x))$. Since $\gcd(d(x), g(x))=1$, we have that $r'\mid \gcd(d(x),G_{2k-2}(x))$. By the inductive hypothesis we know that $\gcd(d(x), G_{2k-2}(x)) = \rho$. Thus, $r'\mid \rho$. It is easy to see that $\gcd(d(x),G_{2k}(x))$ divides $r'$. So, $r'=\gcd(G_2(x), d(x))$.

We observe that for a GFP of Fibonacci type it holds that $G_2^{\prime}(x)=a(x)+b(x)=d(x)$. So, it is clear that $\gcd(G_{2n}^{\prime}(x),d(x))=d(x)$. For a GFP of Lucas type it holds that $G_0^{*}(x)$ is a non-zero constant. Since $G_2^{*}(x)=d(x)G_1^{*}(x)+G_{0}^{*}g(x)$, and $\gcd(d(x), g(x))=1$, we have $$\gcd(d(x),G_2^{*}(x))=\gcd(d(x),d(x)G_1^{*}(x)+G_{0}^{*}g(x))=\gcd(d(x),G_0^{*}(x)g(x))=1.$$

Proof of part (3). We now prove that $\gcd(g(x), G_1(x))=1$ by cases. If $G_1(x)$ is of the Fibonacci type, the conclusion is straightforward. As a second case we suppose that $G_1(x)$ is of the Lucas type. That is $G_1(x)$ satisfies the Binet formula (\[bineformulados\]). Therefore, we have that $$\gcd(g(x), G_1(x))=\gcd(g(x), L_1(x)) = \gcd(g(x), [a+b]/\alpha)=\gcd(g(x), d(x)/\alpha).$$ Since $\gcd(g(x), d(x))=1$, we have that $\gcd(g(x), d(x)/\alpha)=1$. This completes the proof.

\[gcdforproposition4\] If $\{G_{n}(x)\}$ is a GFP polynomial sequence, then for every positive integer $n$ it holds that

(1) $\gcd(G_{n}(x), G_{n+1}(x))$ divides $\gcd(G_{n}(x),g(x)G_{n-1}(x))=\gcd(G_{n}(x),G_{n-1}(x))$,

(2) $\gcd(G_{n}(x), G_{n+2}(x))$ divides $\gcd(G_{n}(x), d(x)G_{n+1}(x))$.

We prove part (1), the proof of part (2) is similar and we omit it. If $r$ is equal to $ \gcd(G_{n}(x), G_{n+1}(x))$, then $r$ divides any linear combination of $G_{n}(x)$ and $G_{n+1}(x)$. Therefore, $r\mid (G_{n+1}(x)-d(x) G_{n}(x))$. This and the recursive definition of $G_{n+1}(x)$ imply that $r\mid g(x)G_{n-1}(x)$. Therefore, $r\mid \gcd(g(x)G_{n-1}(x),G_{n}(x))$. Since $\gcd(g(x),G_{n}(x))=1$, we have that $\gcd(g(x)G_{n-1}(x),G_{n}(x))=\gcd(G_{n-1}(x),G_{n}(x))$. This completes the proof.

\[gcddistance1;2\] Let $m$ and $n$ be positive integers with $0<|m-n|\le 2$.

(1) If $\{G_{t}^{*}(x)\}$ is a GFP of Lucas type, then $$\gcd(G_m^{*}(x),G_n^{*}(x))=
     \begin{cases}
             G_{1}^{*}(x), & \mbox{if $m$ and $n$ are both odd;} \\
             1, & \mbox{otherwise. }
    \end{cases}$$

(2) If $\{G_{t}^{\prime}(x)\}$ is a GFP of Fibonacci type, then $$\gcd(G_m^{\prime}(x),G_n^{\prime}(x))=
     \begin{cases}
            G_{2}^{\prime}(x) & \mbox{if $m$ and $n$ are both even;} \\
             1, & \mbox{otherwise. }
    \end{cases}$$

We prove part (1) using several cases based on the values of $m$ and $n$. The proof of part (2) is similar and we omit. We first provide the proof for the case when $m$ and $n$ are consecutive integers using induction on $m$. Let $S(m)$ be the statement $$\gcd(G_{m}^{*}(x), G_{m+1}^{*}(x))=1\text{  for } m\ge 1.$$ First we prove $S(1)$. From Lemma \[gcdforproposition4\] part (1), we know that $$\label{formula1:for:gcddistance1;2}
\gcd(G_{1}^{*}(x),G_{2}^{*}(x)) \text{ divides } \gcd(G_{1}^{*}(x), g(x)G_{0}^{*}(x)).$$ Since $$\gcd(G_{0}^{*}(x),G_{1}^{*}(x))=\gcd(p_{0}(x),p_{1}(x))=1,$$ we have that $$\gcd(G_{1}^{*}(x),g(x)G_{0}^{*}(x))=\gcd(G_{1}^{*}(x),g(x)).$$ This, (\[formula1:for:gcddistance1;2\]) and Lemma \[gcdlemmas\] part (3) imply that $\gcd(G_{1}^{*}(x),G_{2}^{*}(x))=1$.

We suppose that $S(m)$ is true for $m=k-1$. Thus, suppose that $\gcd(G_{k-1}^{*}(x),G_{k}^{*}(x))=1$. We prove that $S(k)$ is true. From Lemma \[gcdforproposition4\] part (1), we know that $$\label{formula2:for:gcddistance1;2}
\gcd(G_{k}^{*}(x),G_{k+1}^{*}(x)) \text{ divides } \gcd(G_{k}^{*}(x), g(x)G_{k-1}^{*}(x)).$$ From Lemma \[gcdlemmas\] part (3) we know that $\gcd(G_{k}^{*}(x),g(x))=1$. So, $$\gcd(G_{k}^{*}(x), g(x)G_{k-1}^{*}(x))= \gcd(G_{k}^{*}(x), G_{k-1}^{*}(x)).$$ This, (\[formula2:for:gcddistance1;2\]) and the inductive hypothesis imply that $\gcd(G_{k}^{*}(x),G_{k+1}^{*}(x)=1$.

We now prove the proposition for consecutive even integers (this proof is actually a direct consequence of the previous proof). From Lemma \[gcdforproposition4\] part (2), we have $\gcd(G_{2k}^{*}(x), G_{2k+2}^{*}(x))$ divides $\gcd(G_{2k}^{*}(x),d(x)G_{2k+1}^{*}(x))$. From Lemma \[gcdlemmas\] part (2) we know that $\gcd(d(x),G_{2k}^{*}(x))=1$. This implies that $\gcd(G_{2k}^{*}(x),d(x)G_{2k+1}^{*}(x))= \gcd(G_{2k}^{*}(x),G_{2k+1}^{*}(x))$. From the previous part –that is, the case when $m$ and $n$ are consecutive integers– of this proof we conclude that $\gcd(G_{2k}^{*}(x),G_{2k+1}^{*}(x))=1$. This proves that $\gcd(G_{2k}^{*}(x), G_{2k+2}^{*}(x))=1$.

Finally we prove the proposition for consecutive odd integers. From the recursive definition of GFP we have that $\gcd(G_{2k+1}^{*}(x),G_{2k-1}^{*}(x))$ equals $$\gcd(d(x)G_{2k}^{*}(x)+g(x)G_{2k-1}^{*}(x),G_{2k-1}^{*}(x))=\gcd(d(x)G_{2k}^{*}(x),G_{2k-1}^{*}(x))$$ From the first case in this proof we know that $\gcd(G_{2k}^{*}(x),G_{2k-1}^{*}(x))=1$. This implies that $\gcd(G_{2k+1}^{*}(x),G_{2k-1}^{*}(x))=\gcd(d(x),G_{2k-1}^{*}(x))$. This and Lemma \[gcdlemmas\] imply that $$\gcd(G_{2k+1}^{*}(x),G_{2k-1}^{*}(x))=\gcd(d(x),G_{2k-1}^{*}(x))=G_1^{*}(x).$$ This completes the proof of part (1).

Identities and other properties of Generalized Fibonacci Polynomials {#mainresults:section}
====================================================================

In this section we present some identities that the GFP satisfy. These identities are required for the proofs of certain divisibility properties of the GFP. The results in this section are proved using the Binet formulas (see Section \[General:Fibonacci:Polynomial\]). Proposition \[divisity:Hogat:property1\] part (1) is a variation of a result proved by Hoggatt and Long [@HoggattLong], similarly Proposition \[divisity:property:fibonacci\] is a variation of a divisibility property proved by them in the same paper.

In 1963 Ruggles [@koshy] proved that $F_{n+m}= F_{n} L_{m}-(-1)^m F_{n-m}$. Proposition \[divisity:Hogat:property1\] parts (2) and (3) are a generalization of this numerical identity. In 1972 Hansen [@hansen] proved that $ 5 F_{m +n - 1}=L_{m} L_{n} + L_{m - 1} L_{n -1} $. Proposition \[divisity:Hogat:property2\] part (1) is a generalization of this numerical identity.

\[divisity:Hogat:property1\] If $\{ G_{n}^{*}(x)\}$ and $\{ G_{n}^{'}(x)\}$ are equivalent GFP sequences, then

(1) $G_{m+n+1}^{'}(x)= G_{m+1}^{'}(x)G_{n+1}^{'}(x)+g(x)G_{m}^{'}(x)G_{n}^{'}(x)$,

(2) if $n\ge m$, then $G_{n+m}^{'}(x)= \alpha G_{n}^{'}(x) G_{m}^{*}(x)-(-g(x))^{m} G_{n-m}^{'}(x)$,

(3) if $n\ge m$, then $G_{n+m}^{'}(x)= \alpha G_{m}^{'}(x)G_{n}^{*}(x) +(-g(x))^{m} G_{n-m}^{'}(x)$.

We prove part (1). We know that $\{ G_{n}^{'}(x)\}$ satisfies the Binet formula (\[bineformulauno\]). That is, $R_n(x)= (a^{n}-b^{n})/(a-b)$ . (Recall that we use $a:=a(x)$ and $b:=b(x)$.)

Therefore, $G_{m+1}^{'}(x)G_{n+1}^{'}(x)+g(x)G_{m}^{'}(x)G_{n}^{'}(x)$ is equal to, $$\left[(a^{m+1}-b^{m+1})(a^{n+1}-b^{n+1})+g(x)(a^{m}-b^{m})(a^{n}-b^{n})\right]/(a-b)^{2}.$$ Simplifying and factoring terms we obtain, $$\left[\left(a^{n+m}(a^2+g(x))+b^{n+m}(b^2+g(x))\right)-(a^nb^m+b^na^m)(ab+g(x))\right]/(a-b)^{2}.$$ Next, since $ab=-g(x)$, we see that the above expression is equal to, $$\left[a^{n+m}(a^2+g(x))+b^{n+m}(b^2+g(x))\right]/(a-b)^{2}.$$ This, with the facts that, $(a^2+g(x))=a(a-b)$ and $(b^2+g(x))=-b(a-b)$, shows that the above expression is equal to $$\left(a^{n+m+1}-b^{n+m+1}\right) /(a-b)=R_{n+m+1}(x).$$

We prove part (2) the proof of part (3) is identical and we omit it. Suppose that $G_{k}^{*}(x)$ is equivalent to $G_{k}^{'}(x)$ and that $G_{k}^{*}(x)$ is of the Lucas type for all $k$. For simplicity let us suppose that $\alpha=1$ (the proof when $\alpha\neq 1$ is similar, so we omit it). Using the Binet formulas (\[bineformulados\]) and (\[bineformulauno\]) we obtain that $G_{n}^{'}(x) G_{m}^{*}(x)-(-g(x))^{m} G_{n-m}^{'}(x)$ equals $$\displaystyle{\frac{(a^{n}-b^{n})(a^{m}+b^{m})-(-g(x))^{m}(a^{n-m}-b^{n-m})}{(a-b)}}.$$ After performing the indicated multiplication and simplifying we obtain that this expression is equal to $$\left[\frac{a^{n+m}-b^{n+m}}{a-b} \right]+ \left[\frac{a^{n}b^{m}-a^{m}b^{n}-(-g(x))^m a^{n-m}+(-g(x))^mb^{n-m}}{a-b}\right].$$ Since $-g(x)=ab$, it is easy to see that the expression in the right bracket is equal to zero. Thus, $(a^{n+m}-b^{n+m})/(a-b)= G_{n+m}^{'}(x)$. This completes the proof of part (2).

\[divisity:Hogat:property2\] Let $\{ G_{n}^{*}(x)\}$ and $\{ G_{n}^{'}(x)\}$ be equivalent GFP sequences. If $m\ge 0$ and $n\ge 0$, then

(1) $(a-b)^2G^{'}_{m+n+1}(x) = \alpha^2 G_{m+1}^{*}(x)G_{n+1}^{*}(x)+\alpha^2 g(x)G_{m}^{*}(x)G_{n}^{*}(x),$

(2) $G_{m+n+2}^{*}(x) = \alpha G_{m+1}^{*}(x)G_{n+1}^{*}(x)+g(x)[\alpha G_{m}^{*}(x)G_{n}^{*}(x)-G_{m+n}^{*}(x)].$

In this proof we use $\alpha=1$, the proof when $\alpha\neq 1$ is similar, so we omit it. (Recall, once again, that we use $a:=a(x)$ and $b:=b(x)$.)

Proof of part (1). Since $ G_{n}^{*}(x)$ is a Fibonacci polynomial of the Lucas type, we have that $G_{n}^{*}(x)$ satisfies the Binet formula $L_n(x)= (a^{n}+b^{n})/\alpha$ given in (\[bineformulados\]). Therefore, $$\label{divisity:Hogat:property2:formula1}
G_{m+1}^{*}(x)G_{n+1}^{*}(x)+g(x)G_{m}^{*}(x)G_{n}^{*}(x)$$ is equal to, $$\left[a^{n+1}+b^{n+1}\right]\left[a^{m+1}+b^{m+1}\right]+g(x)\left[a^{n}+b^{n}\right]\left[a^{m}+b^{m}\right].$$ Simplifying and factoring we see that this expression is equal to $$a^{m+n}\left[a^2+g(x)\right]+b^{m+n}\left[b^2+g(x)\right]+(ab+g(x))\left[a^mb^n+a^nb^m\right].$$ Since $$ab=-g(x),\; a^2+g(x)=a(a-b),\text{ and } b^2+g(x)=-b(a-b),$$ we have that the expression in (\[divisity:Hogat:property2:formula1\]) is equal to $(a-b)(a^{m+n+1}-b^{m+n+1})$. We recall that $G_{m+n+1}^{'}(x)$ is equivalent to $G_{m+n+1}^{*}(x)$. Thus, $G^{'}_{m+n+1}(x) =(a^{m+n+1}-b^{m+n+1})/(a-b)$. Therefore, $(a-b)^2G^{'}_{m+n+1}(x) =(a-b)\left[a^{m+n+1}-b^{m+n+1}\right]$. This completes the proof of part (1).

Proof of part (2). From the proof of part (1) we know that $$(a-b)^2G^{'}_{m+n+1}(x)=(a-b)[a^{m+n+1}-b^{m+n+1}].$$ Simplifying the right side of the previous equality we have that $$(a-b)^2G^{'}_{m+n+1}(x)=a^{m+n+2}-ba^{m+n+1}- ab^{m+n+1} + b^{m+n+2}.$$ So, $(a-b)^2G^{'}_{m+n+1}(x)=a^{m+n+2}+ b^{m+n+2} -ab[a^{m+n}+ b^{m+n}]$. We recall that $ab=-g(x)$. Thus, $$(a-b)^2G^{'}_{m+n+1}(x)=a^{m+n+2}+ b^{m+n+2} + g(x)[a^{m+n}+ b^{m+n}].$$ This and the Binet formula (\[bineformulados\]), imply that $$(a-b)^2G^{'}_{m+n+1}(x)=G_{m+n+2}^{*}(x) + g(x)G_{m+n}^{*}(x).$$ So, the proof follows from part (1) of this Proposition.

\[Dic2\] Let $\{ G_{n}^{*}(x)\}$ be a GFP sequence of the Lucas type. If $m$, $n$, $r$, and $q$ are positive integers, then

(1) if $m\leq n$, then $G_{m+n}^{*}(x)=\alpha G_{m}^{*}(x)G_{n}^{*}(x)+(-1)^{m+1}(g(x))^mG_{n-m}^{*}(x)$,

(2) if $r<m$, then there is a polynomial $T(x)$ such that $$G_{mq+r}^{*}(x)=
        \left\{
             \begin{array}{ll}
                G_{m}^{*}(x)T(x)+(-1)^{m(t-1)+t+r}(g(x))^{(t-1)m+r} G_{m-r}^{*}(x), & \hbox{ if } $q$ \hbox{ is odd;} \\
                G_{m}^{*}(x)T(x)+(-1)^{(m+1)t}(g(x))^{mt} G_{r}^{*}(x),             & \hbox{ if }  $q$ \hbox{ is even}
            \end{array}
        \right.$$

    where $t=\left\lceil \frac{q}{2} \right\rceil$,

(3) if $n>1$, then there is a polynomial $T_n(x)$ such that $$G_{2^nr}^{*}(x)= G_{r}^{*}(x)T_n(x)+(2/\alpha)(g(x))^{2^{n-1}r}.$$

We prove part (1). Since $G_{m}^{*}(x)$ and $G_{n}^{*}(x)$ are of the Lucas type, they both satisfy the Binet formula (\[bineformulados\]). Thus, $$G_{m}^{*}(x)G_{n}^{*}(x)=\left(\frac{a^m+b^m}{\alpha}\right)\left(\frac{a^n+b^n}{\alpha}\right)
=\frac{a^{m+n}+b^{m+n}}{\alpha^2}+\frac{(ab)^{m}\left(a^{n-m}+b^{n-m}\right)}{\alpha^2}.$$ So, $G_{m}^{*}(x)G_{n}^{*}(x)=\left[G_{n+m}^{*}(x)+(ab)^mG_{n-m}^{*}(x)\right]/\alpha.$ This and $ab=-g(x)$, imply that $$G_{m+n}^{*}(x)=\alpha G_{m}^{*}(x)G_{n}^{*}(x)-(-g(x))^{m} G_{n-m}^{*}(x).$$ This completes the proof of part (1).

We first prove part (2) when $q$ is odd by induction. Suppose $q=2t-1$, and let $S(t)$ be the following statement. For every positive integer $t$ there is a polynomial $T_t(x)$ such that $$G_{m(2t-1)+r}^{*}(x)=G_{m}^{*}(x)T_t(x)+(-1)^{m(t-1)+t+r}(g(x))^{(t-1)m+r} G_{m-r}^{*}(x).$$ From part (1), taking $T_1(x)=\alpha G_{r}^{*}(x)$, it is easy to see that $S(t)$ is true if $t=1$.

We suppose that $S(k)$ is true. That is, suppose that there is a polynomial $T_{k}(x)$ such that $$\label{formula1:for:Dic2}
G_{m(2k-1)+r}^{*}(x)=G_{m}^{*}(x)T_k(x)+(-1)^{m(k-1)+t+r}(g(x))^{(k-1)m+r} G_{m-r}^{*}(x).$$

We prove that $S(k+1)$ is true. Notice that $G_{m(2k+1)+r}^{*}(x)=G_{(2km+r)+m}^{*}(x)$. Therefore, from part (1) we have $$G_{m(2k+1)+r}^{*}(x)=\alpha G_{m}^{*}(x)G_{2km+r}^{*}(x)+(-1)^{m+1}g^m(x)G_{m(2k-1)+r}^{*}(x).$$ This and $S(k)$ (see (\[formula1:for:Dic2\])), imply that $G_{m(2(k+1)+r}^{*}(x)$ equals $$\alpha G_{m}^{*}(x)G_{2km+r}^{*}(x)+(-1)^{m+1}(g(x))^{m}G_{m}^{*}(x)T_k (x)+(-1)^{km+(t+1)+r}(g(x))^{km+r} G_{m-r}^{*}(x).$$ Therefore, $G_{m(2(k+1)+r}^{*}(x)$ equals $$G_{m}^{*}(x)[\alpha G_{2km+r}^{*}(x)+(-1)^{m+1}(g(x))^{m}T_k (x)]+(-1)^{km+(t+1)+r}(g(x))^{km+r} G_{m-r}^{*}(x).$$ This, with $T_{k+1}(x):=\alpha G_{2km+r}^{*}(x)+(-1)^{m+1}(g(x))^mT_k (x)$, implies $S(k+1)$. This complete the proof when $q$ is odd.

We now prove part (2) when $q$ is even by induction –this proof is similar to the case when $q$ is odd–. Suppose $q=2t$, and let $H(t)$ be the following statement. For every positive integer number there is a polynomial $T_t(x)$ such that $$G_{m(2t)+r}^{*}(x)=G_{m}^{*}(x)T_t(x)+(-1)^{(m+1)t}(g(x))^{mt} G_{r}^{*}(x).$$ From part (1), taking $T_1(x)=\alpha G_{r}^{*}(x)$, it is easy to see that $H(t)$ is true if $t=1$.

We suppose that $H(k)$ is true. That is, suppose that there is a polynomial $T_{k}(x)$ such that $$\label{formula2:for:Dic2}
G_{m(2k)+r}^{*}(x)=G_{m}^{*}(x)T_k(x)+(-1)^{(m+1)k}(g(x))^{mk} G_{r}^{*}(x).$$

We prove that $H(k+1)$ is true. Notice that $G_{2m(k+1)+r}^{*}(x)=G_{((2k+1)m+r)+m}^{*}(x)$. Therefore, from part (1) we have that $$G_{2m(k+1)+r}^{*}(x)=\alpha G_{m}^{*}(x)G_{(2k+1)m+r}^{*}(x)+(-1)^{m+1}(g(x))^m G_{2mk+r}^{*}(x).$$ This and $H(k)$ (see (\[formula2:for:Dic2\])), imply that $G_{m(2(k+1))+r}^{*}(x)$ equals $$\alpha G_{m}^{*}(x)G_{(2k+1)m+r}^{*}(x)+(-1)^{m+1}(g(x))^mG_{m}^{*}(x)T_{k} (x)+(-1)^{(k+1)(m+1)}(g(x))^{m(k+1)}G_{r}^{*}(x).$$ Therefore, $G_{m(2(k+1))+r}^{*}(x)$ equals $$G_{m}^{*}(x) \left[\alpha G_{(2k+1)m+r}^{*}(x)+(-1)^{m+1}(g(x))^mT_{k} (x)\right]+(-1)^{(m+1)(k+1)}(g(x))^{m(k+1)} G_{r}^{*}(x).$$ This with $T_{k+1}(x):=\alpha G_{(2k+2)m+r}^{*}(x)+(-1)^{m}(g(x))^mT_{k} (x)$, implies $H(k+1)$.

We finally prove part (3) by induction. Since $G_{n}^{*}(x)$ is of the Lucas type, by the Binet formula it is easy to see that $G_0(x)=2/\alpha$. Let $S(n)$ be the statement: for every positive integer $n$ there is a polynomial $T_n(x)$ such that $G_{2^nr}^{*}(x)= G_{r}^{*}(x)T_n(x)+(2/\alpha)g^{2^{n-1}r}(x)$.

Proof of $S(2)$. From part (1) we have $G_{2^2r}^{*}(x)= G_{2r+2r}^{*}(x)=\alpha(G_{2r}^{*}(x))^2-(2/\alpha)(g(x))^{2r}$. Applying again the result in part (1) for $G_{2r}^{*}(x)$ (and simplifying) we obtain $$\begin{aligned}
G_{2^2r}^{*}(x)&=&\alpha[\alpha(G_{r}^{*}(x))^2-\frac{2}{\alpha}(-g(x))^{r}]^2-\frac{2}{\alpha}(g(x))^{2r}\\
&=&G_{r}^{*}(x)[\alpha^3(G_{r}^{*}(x))^3+(-1)^{r+1}4\alpha G_r^{*}(x)(g(x))^{r}]+\frac{4}{\alpha}(g(x))^{2r} -\frac{2}{\alpha}(g(x))^{2r}\\
&=&G_{r}^{*}(x)T_2(x)+\frac{2}{\alpha}(g(x))^{2r}.\end{aligned}$$ where $T_2(x)=\alpha^3(G_{r}^{*}(x))^3+(-1)^{r+1}4\alpha G_{r}^{*}(x)(g(x))^{r}$. This proves $S(2)$.

We suppose that $S(k)$ is true for $k>2$, and we prove $S(k+1)$ is true. That is, we suppose that for a fixed $k$ there is a polynomial $T_k(x)$ such that $$G_{2^kr}^{*}(x)= G_{r}^{*}(x)T_k(x)+(2/\alpha)g^{2^{k-1}r}(x).$$ From part (1) we have $G_{2^{k+1}r}^{*}(x)= G_{2^k r+2^k r}^{*}(x)=\alpha(G_{2^k r}^{*}(x))^2-(2/\alpha)(g(x))^{2^k r}$. Using the result from the inductive hypothesis $S(k)$ and simplifying, we obtain $$\begin{aligned}
G_{2^{k+1}r}^{*}(x)&=&\alpha[ G_{r}^{*}(x)T_k(x)+\frac{2}{\alpha}(g(x))^{2^{k-1} r} ]^2-\frac{2}{\alpha}(g(x))^{2^k r}\\
&=&G_{r}^{*}(x)[\alpha G_{r}^{*}(x)T_k ^2(x)+4T_k(x)(g(x))^{2^{k-1} r} ]+\frac{4}{\alpha}(g(x))^{2^k r} -\frac{2}{\alpha}(g(x))^{2^kr}\\
&=&G_{r}^{*}(x)T_{k+1}(x)+\frac{2}{\alpha}(g(x))^{2^kr},\end{aligned}$$ where $T_{k+1}(x)=\alpha G_{r}^{*}(x)T_k ^2(x)+4T_k(x)(g(x))^{2^{k-1} r} $. This completes the proof of part (3).

In the following part of this section, we present two divisibility properties for the GFP.

\[divisity:property:fibonacci\] If $\{ G_{n}^{'}(x)\}$ is a GFP sequence of the Fibonacci type, then $G_{m}^{'}(x)$ divides $G_{n}^{'}(x)$ if and only if $m$ divides $n$.

We first prove the sufficiency. Based on the hypothesis that $m$ divides $n$, there is an integer $q\ge1$ such that $n=mq$. Then, using the Binet formula (\[bineformulauno\]), we have that,

$$G_{m}^{'}(x)=(a^m-b^m)/(a-b)\,\, \text{  and  }\,\, G_{mq}^{'}(x)=(a^{mq}-b^{mq})/(a-b).$$

It is easy to see –using induction on $q$– that $(a^m-b^m)$ divides $(a^{mq}-b^{mq})$ which implies that $G_{m}^{'}(x)$ divides $G_{mq}^{'}(x)$. This proves the sufficiency.

We now prove the necessity. Suppose that $m$ does not divide $n$ and that $G_{m}^{'}(x)$ divides $G_{n}^{'}(x)$ for $m$ and $n$ greater than $1$. Therefore, there integers $q$ and $r$ with $0<r<n$ such that $n=mq+r$. Then by Proposition \[divisity:Hogat:property1\] part (1) $$\begin{aligned}
  G_{n}^{'}(x) &=& G_{mq+r}^{'}(x) \\
   &=& G_{mq+1}^{'}(x)G_{r}^{'}(x)+g(x)G_{mq}^{'}(x)G_{r-1}^{'}(x)\\
   &=& \left(d(x)G_{mq}^{'}(x)+g(x)G_{mq-1}^{'}(x)\right)G_{r}^{'}(x)+g(x)G_{mq}^{'}(x)G_{r-1}^{'}(x)\\
   &=& d(x)(x) G_{mq}^{'}(x) G_{r}^{'}(x)+g(x)G_{mq-1}^{'}(x)G_{r}^{'}(x)+g(x)G_{mq-1}^{'}(x)G_{r}^{'}(x).\end{aligned}$$ Grouping terms and simplifying we obtain, $$G_{n}^{'}(x)=G_{mq}^{'}(x)G_{r+1}^{'}(x)+g(x)G_{mq-1}^{'}(x)G_{r}^{'}(x).$$ This and the fact that $G_{m}^{'}(x)\mid G_{n}^{'}(x)$ and $G_{m}^{'}(x) \mid G_{mq}^{'}(x)$ imply that $$G_{m}^{'}(x)\mid g(x)G_{mq-1}^{'}(x)G_{r}^{'}(x).$$ From Lemma \[gcdlemmas\] part (3) and Proposition \[gcddistance1;2\] we know that $\gcd(G_{mq}^{'}(x),g(x))=1$ and $\gcd(G_{mq-1}^{'}(x), G_{mq}^{'}(x))=1$, respectively. This implies that $G_{m}^{'}(x)\mid G_{r}^{'}(x).$ That is a contradiction since degree ($G_{r-1}^{'}(x))<$ degree $(G_{m-1}^{'}(x))$. This completes the proof.

\[divisibity:property:first:type\] Let $m$ be a positive integer that is not a power of two. If $G_{m}^{*}(x)$ is a GFP of Lucas type, then for all odd divisors $q$ of $m$, it holds that $G_{m/q}^{*}(x)$ divides $G_{m}^{*}(x)$. More over $G_{m/q}^{*}(x)$ is of the Lucas type.

Let $q$ be an odd divisor of $m$. If $q=1$ the result is obvious. Let us suppose that $q\not = 1$. Therefore, there is an integer $d>1$ such that $m=dq$. Using the Binet formula (\[bineformulados\]), where $a:=a(x)$ and $b:=b(x)$, we have $G_{m}^{*}(x)=G_{dq}^{*}(x)=(a^{dq}+b^{dq})/\alpha$. Let $X=a^{d}$ and $Y=b^{d}$. Using induction it is possible to prove that $X+Y$ divides $X^q+Y^q$. This implies that there is a polynomial $Q(x)$ such that $(X^q+Y^q)/\alpha=Q(x)(X+Y)/\alpha$. Therefore, $$G_{m}^{*}(x)=G_{dq}^{*}(x)=(a^{dq}+b^{dq})/\alpha=Q(x)(a^{d}+b^{d})/\alpha.$$ This and the Binet formula (\[bineformulados\]) imply that $G_{m}^{*}(x)=G_{d}^{*}(x) Q(x)$.

Characterization of the strong divisibility property {#gcd:characterization}
====================================================

In this section we prove the main results of this paper. Thus, we prove the necessary and sufficient condition for the strong divisibility property for generalized Fibonacci polynomial of the Fibonacci type. We also prove that the strong divisibility property holds partially for generalized Fibonacci polynomial of the Lucas type. The other important result in this section is that the strong divisibility property holds partially for a generalized Fibonacci polynomial and its equivalent. The results here therefore provide a complete characterization of the strong divisibility property satisfied by the GFP of Fibonacci type.

We note that if $G_{m}^{*}(x)$ and $G_{n}^{\prime}(x)$ are two equivalent polynomial from Table \[equivalent\], then $\gcd(G_{m}^{*}(x), G_{n}^{'}(x))$ is either one or $G_{\gcd(m,n)}^{*}(x)$. However, it is not true in general. Here we give an example of a couple GFP polynomials that do not satisfies this property. Firstly we define a Fibonacci type polynomial $$G_0^{\prime}(x)=0, \; G_1^{\prime}(x)= 1,\;  \text{and} \;  G_{n}^{\prime}(x)= (2x+1) G_{n - 1}^{\prime}(x) + G_{n - 2}^{\prime}(x) \text{ for } n\ge 2.$$ We now define the equivalent polynomial of the Lucas type $$G_0^{*}(x)=2, \; G_1^{*}(x)= 2x+1,\;  \text{and} \;  G_{n}^{*}(x)= (2x+1) G_{n - 1}^{*}(x) + G_{n - 2}^{*}(x) \text{ for } n\ge 2.$$ After some calculations we can see that $\gcd(G_{m}^{*}(x), G_{n}^{'}(x))$ is one, two or $G_{\gcd(m,n)}^{*}(x)$. Using the same polynomials we can see also that $\gcd(G_{m}^{*}(x), G_{n}^{*}(x))$ is one, two or $G_{\gcd(m,n)}^{*}(x)$. If we do the same calculations for numerical sequences (Fibonacci and Lucas numbers), we can see that they have the same behaviour.

In this section we use the notation $E_{2}(n)$ to represent the *integer exponent base two* of a positive integer $n$ which is defined to be the largest integer $k$ such that $2^{k}\mid n$.

\[Dic1\] If $R(x)$, $S(x)$ and $T(x)$ are polynomial in $\mathbb{Z}[x]$, then $$\gcd(R(x),T(x))=\gcd(R(x),R(x)S(x)-T(x)).$$

\[propiedadDivision\] Let $\{ G_{n}^{*}(x)\}$ be a GFP sequence of the Lucas type. If $m \mid n$ and $E_2(n)=E_{2}(m)$, then $
\gcd(G_{n}^{*}(x),G_{m}^{*}(x))=G_{m}^{*}(x).
$

First of all we recall that $E_{2}(n)$ is the largest integer $k$ such that $2^{k}\mid n$. We suppose that $n=mq$ with $q\in\mathbb{N}$. Since $E_{2}(m)=E_{2}(n)=E_{2}(mq)$, we conclude that $q$ is odd. This, Lemma \[Dic1\] and Proposition $\ref{Dic2}$ part (2) imply that $$\begin{aligned}
\gcd(G_{n}^{*}(x),G_{m}^{*}(x))&=&\gcd(G_{qm}^{*}(x),G_{m}^{*}(x))\\
&=&\gcd (G_{m}^{*}(x)T(x)+(-1)^{(n-1)m+n}(g(x))^{(n-1)m} G_{m}^{*}(x),G_{m}^{*}(x))\\
&=&G_{m}^{*}(x).   \hspace{10.1cm}\end{aligned}$$ This proves the proposition.

\[divisity:property:firstype\] Let $G_{m}^{*}(x)$ be a GFP of Lucas type. If $m>0$ is not a power of two, then for all odd divisors $q$ of $m$, it follows that $G_{m/q}^{*}(x)$ divides $G_{m}^{*}(x)$. More over $G_{m/q}^{*}(x)$ is of the Lucas type.

It is easy to see that $E_2(m/q)=E_2(m)$. Therefore, the conclusion follows by Proposition \[propiedadDivision\].

\[propiedadDivisioncase2\] Let $d_{k}=\gcd(G_0 ^*(x),G_{k} ^{*}(x))$ where $G_{k}^{*}(x)$ is GFP of the Lucas type. Suppose that there is an integer $k'>0$ such that $d_{k'}=2$. If $m$ is the minimum positive integer such that $d_{m}=2$, then $m|n$ if and only if $d_{n}=2$.

We suppose $m$ is the minimum positive integer such that $d_{m}=2$. Suppose that $m|n$, by Proposition \[propiedadDivision\] we know that $\gcd(G^* _{m}(x),G_{n}^{*}(x))=G_{m}^{*}(x)$ (we recall that $G^*_{0}(x)=p_0(x)$ and $|p_0(x)|=1$ or $2$). This and the fact that $2|G_{m} ^*(x)$, implies that $\gcd(G_{0} ^*(x),G_{n} ^*(x))=2$. This proves that $d_{n}=2$.

Suppose that there is $n\in \mathbb{N}-\{m\}$ that satisfies that $d_{n}=2$ (note $2|\gcd(G^{*}_{m}(x),G_{n} ^*(x)$). From the division algorithms we have that there are integer $q$ and $r$ such that $n=mq+r$ where $0\le r< m$. This and Proposition \[Dic2\] part (2), imply that $$\gcd(G^{*} _{m}(x),G_{n} ^*(x))=
    \left\{
         \begin{array}{ll}
            \gcd(G^* _{m}(x),(g(x))^{(t-1)m+r} G_{m-r}^{*}(x)) & \hbox{ if } $q$ \hbox{ is odd;} \\
            \gcd(G^* _{m}(x),(g(x))^{mt} G_{r}^{*}(x))             & \hbox{ if }  $q$ \hbox{ is even.}
        \end{array}
    \right.$$ This, Lemma \[gcdlemmas\] part (3), implies that $\gcd(G^* _{m}(x),G_{n} ^*(x))$ is either $\gcd(G^* _{m}(x),G_{m-r}^{*}(x))$ or $\gcd(G^* _{m}(x),G_{r}^{*}(x))$. From this and the fact that $2|\gcd(G^* _{m}(x),G_{n} ^*(x))$, we have that $\gcd(G^* _{r}(x),G^* _{0}(x))=2$ or $\gcd(G^* _{m-r}(x),G^*_{0}(x))=2$ . This holds only if $r=0$, due to definition of $m$. Therefore, $n=mq$.

\[fundamental\] Let $G_{k}^{*}(x)$ be a GFP of Lucas type and let $n=mq+r$ where $m, q$ and $r$ are positive integers with $r<m$. If $m_1= m-r$ when $q$ is odd and $m_1=r$ when $q$ is even, then $
\gcd(G_{n}^{*}(x),G_{m}^{*}(x))=\gcd (G_{m_1}^{*}(x),G_{m}^{*}(x)).
$

Let $$f(x)=
 \begin{cases}
         (-1)^{m(t-1)+t+r}(g(x))^{(t-1)m+r} , & \mbox{ if  $q$ is odd;}\\
        (-1)^{(m+1)t}(g(x))^{mt},  & \mbox{ if  $q$   is even.}
\end{cases}$$ This and Lemma \[gcdlemmas\] part (3) imply that $\gcd(G_{m}^{*}(x),f(x))=1$. Therefore, by Proposition \[Dic2\] part (2) it follows that $\gcd(G_{mq+r}^{*}(x),G_{m}^{*}(x))=\gcd (G_{m}^{*}(x)T(x)+f(x)G_{m_1}^{*}(x),G_{m}^{*})$. Now it is easy to see that $$\gcd (G_{m}^{*}(x)T(x)+f(x)G_{m_1}^{*}(x),G_{m}^{*})=\gcd (f(x) G_{m_1}^{*}(x),G_{m}^{*}(x)).$$ Since $\gcd(G_{m}^{*}(x),f(x))=1$, by Proposition \[prop2;1\] part (1) we have $\gcd (f(x) G_{m_1}^{*}(x),G_{m}^{*}(x))=\gcd (G_{m_1}^{*}(x),G_{m}^{*}(x))$.

\[second:main:thm\] Let $\{ G_{n}^{*}(x)\}$ be a GFP of the Lucas type. If $m$ and $n$ are positive integers and $d=\gcd(m,n)$, then $$\gcd(G_{m}^{*}(x),G_{n}^{*}(x))= \begin{cases} G_{d}^{*}(x)  & \mbox{ if }\;   E_{2}(m)= E_{2}(n);\\
                                                    \gcd(G_{d}^*(x),G_{0}^*(x))   & \mbox{ otherwise}.
                            \end{cases}$$

First of all we prove the result for $E_{2}(n)=E_{2}(m)$. From the Euclidean algorithm we know that there are non-negative integers $q$ and $r$ such that $n=mq+r$ with $r<m$. Let $d=\gcd(m,n)$. Clearly, if $r=0$, then $d=m$. Therefore, the result holds by Proposition \[propiedadDivision\].

We suppose that $r\neq 0$. If we take $m_1$ as in Lemma \[fundamental\], then $$\gcd (G_{n}^{*}(x),G_{m}^{*}(x))=\gcd(G_{mq+r}^{*}(x),G_{m}^{*}(x))=\gcd (G_{m_1}^{*}(x),G_{m}^{*}(x)).$$ Let $M_1=\{m,m_1 \}$. Notice that $\gcd(m_1,m)=d$, $E_2(m)=E_2(m_1)$ and that $m_1<m$. Therefore, there are non-negative integers $q_1$ and $r_1$ such that $m=m_1q_1+r_1$ with $r_1<m_1$. Again, if $r_1=0$, by Proposition \[propiedadDivision\] we obtain that $
\gcd(G_{n}^{*}(x),G_{m}^{*}(x))=\gcd(G_{m}^{*}(x),G_{m_1}^{*}(x))=G_{d}^{*} (x).
$ If $r_1\neq 0$ we repeat the previous step and then we can guarantee that $$\gcd (G_{n}^{*}(x),G_{m}^{*}(x))=\gcd (G_{m_1}^{*}(x),G_{m}^{*}(x))=\gcd (G_{m_1}^{*}(x),G_{m_2}^{*}(x)),$$ where $$m_2=\begin{cases}m_1-r_1 & \mbox{ if $q$ is odd};\\
                    r_1  & \mbox{ if } \mbox{ if $q$ is even}.
             \end{cases}$$ We repeat this procedure $t$ times until we obtain the ordered decreasing sequence $m>m_1>m_2>\cdots >m_t\geq d$ such that $E_2(m)=E_2(m_t)$ and $\gcd(m_t,m_{t-1})=d$, where $$m_t=\begin{cases}m_{t-1}-r_{t-1} & \mbox{ if $q$ is odd};\\
                    r_{t-1}  & \mbox{ if } \mbox{ if $q$ is even}.
             \end{cases}$$ Notice that $M_t=\{m, m_1, m_2, \ldots, m_t\} =M_{t-1}\cup\{m_t\}$ is an ordered set of natural numbers, therefore there is a minimum element. Since $M_t$ is constructed with a sequence of decreasing positive integer numbers, there must be an integer $k$ such that $M_{t}\subset M_k$ for all $t<k$ and $M_{k+1}$ is undefined. Thus, the procedure ends with $M_k$. Note that $m>m_1>m_2>\cdots >m_k \geq d$ such that $E_2(m)=E_2(m_k)$ and $\gcd(m_k,m_{k-1})=d$.

[**Claim**]{}. The minimum element of $M_k$ is $m_k=d$ and $m_{k}\mid m_{k-1}$.

Proof of claim. From the Euclidean algorithm we know that there are non-negative integers $q_k$ and $r_k$ such that $m_{k-1}=m_kq_k+r_k$ with $r_k<m_k$. If $r_k\neq 0$ we can repeat the procedure describe above to obtain a new set $M_{k+1}$ with $M_{k} \subset M_{k+1}$. That is a contradiction. Therefore, $r_k=0$. So, $m_{k-1}=m_kq_k$. This implies that $\gcd(m_k,m_{k-1})=d$. Thus, $m_k=d$. This proves the claim.

The Claim and the Proposition \[propiedadDivision\] allow us to conclude that $$\gcd (G_{n}^{*}(x),G_{m}^{*}(x))=\gcd (G_{m}^{*}(x),G_{m_1}^{*}(x))=\cdots=\gcd (G_{m_{k-1}}^{*}(x),G_{m_{k}}^{*}(x))=G_{d}^{*}.$$

We now prove by cases that $\gcd (G_{n}^{*}(x),G_{m}^{*}(x))=\gcd (G_{d}^{*}(x),G_{0}^{*}(x))$ if $E_{2}(n)\neq E_{2}(m)$ and $d=\gcd(n,m)$.

**Case 1.** Suppose that $m<n$ and that $E_2(n)<E_2(m)$. From the Euclidean algorithm there are two non-negative integers $q$ and $r$ such that $n=mq+r$ with $r<m$. Let $m_1= m-r$ when $q$ is odd and $m_1=r$ when $q$ is even (as defined as in Lemma \[fundamental\]). Since $n=mq+r$ and $E_2(n)<E_2(m)$, we have that $r\neq 0$. It is easy to see that $E_2(n)=E_2(r)$, and therefore $E_2(n)=E_2(m_1)$. This and Lemma \[fundamental\] imply that $
\gcd (G_{n}^{*}(x),G_{m}^{*}(x))=\gcd (G_{m}^{*}(x),G_{m_1}^{*}(x)).
$ Since $E_2(m_1)=E_2(n)<E_2(m)$ and $m_1<m$, the criteria for Case 2 are satisfied here, so the proof of this case may be completed as we are going to do in Case 2 below.

**Case 2.** Suppose that $E_2(m)<E_2(n)$ and that $m<n$. From the Euclidean algorithm we know that there are two non-negative integers $r$ and $q$ such that $n=mq+r$ with $ r<m$. If $r=0$, then $q$ must be even (because $E_2(m)<E_2(n)$). Let $k=E_2(q)$ and we consider two subcases on $k$.

**Subcase 1.** If $k=1$, then $q=2t$ where $t$ is odd. Therefore, by the Proposition \[Dic2\] part (1) we have that $
    G_{n}^{*}(x)=G_{2mt}^{*}(x)=\alpha (G_{mt}^{*}(x))^2+(-1)^{mt+1}(G_0 ^*(x))(-g(x))^{mt}.
    $ This, Proposition \[propiedadDivision\], Lemma \[gcdlemmas\] part (3) and Lemma \[Dic1\] imply that

$$\begin{aligned}
    \gcd (G_{n}^{*}(x),G_{m}^{*}(x))&=& \gcd\left(\alpha (G_{mt}^{*}(x))^2+(-1)^{mt+1}G_0 ^*(x)(-g(x))^{mt}, G_{m}^{*}(x)\right) \\
                            &=& \gcd((-1)^{mt+1}G_0 ^*(x)(-g(x))^{mt},G_{m}^{*}(x)) \\
                                                        &=& \gcd(G_0 ^*(x),G_{m}^{*}(x))\\
                                                        &=& \gcd(G_0 ^*(x),G_{d}^{*}(x)).
    \end{aligned}$$

**Subcase 2.** If $k>1$, then $q=2^kt$ where $t$ is odd. Therefore, by the Proposition \[Dic2\] part (3), there is a polynomial $T_k(x)$ such that $
    G_{n}^{*}=G_{2^kmt}^{*}=G_{mt}^{*}(x)T_k(x)+G_0 ^*(x)g^{2^{k-1}mt}(x).
    $ This, Proposition \[propiedadDivision\], Lemma \[gcdlemmas\] part (3) and Lemma \[Dic1\] imply $$\begin{aligned}
    \gcd (G_{n}^{*}(x),G_{m}^{*}(x))&=& \gcd(G_{mt}^{*}(x)T_k(x)+G_0 ^*(x) g^{2^{k-1}mt}(x) , G_{m}^{*}(x)) \\
                            &=& \gcd(G_0 ^*(x) g^{2^{k-1}mt}(x) ,G_{m}^{*}(x)) \\
                            &=&\gcd(G_0 ^*(x) ,G_{m}^{*}(x))\\
                                                        &=& \gcd(G_0 ^*(x),G_{d}^{*}(x)).
    \end{aligned}$$

Let us now suppose that $r\neq 0$. This and Lemma \[fundamental\], imply that $
\gcd (G_{n}^{*}(x),G_{m}^{*}(x))=\gcd (G_{m}^{*}(x),G_{m_1}^{*}(x)),
$ where $m_1= m-r$ when $q$ is odd and $m_1=r$ when $q$ is even (as defined as in Lemma \[fundamental\]). Therefore, $m_1<m<n$ and $\gcd(m,n)=\gcd(m,m_1)=d$.

We analyze both, the case in which $m_1\mid m$ and the case in which $m_1 \nmid m$. Suppose that $m=m_1 q_2$ and we consider two cases for $q_2$.

**Subcase $q_2$ is odd.** If $q_2$ is odd we have that $E_2(m_1)=E_2(m)$. Therefore, by Proposition \[propiedadDivision\] we obtain that $$\gcd(G_{m}^{*}(x),G_{n}^{*}(x))=\gcd(G_{m}^{*}(x),G_{m_1}^{*}(x))=G_{d}^{*}(x)\; \text{ and }\; E_{2}(G_{d}^{*}(x))<E_{2}(G_{n}^{*}(x)).$$ This imply that $\gcd(G_{m}^{*}(x),G_{n}^{*}(x))=\gcd(G_{d}^{*}(x),G_{0}^{*}(x))$.

**Subcase $q_2$ is even.** If $q_2$ is even, then $E_2(m_1)<E_{2}(m)$. Now it is easy to see that $\gcd(G_{m}^{*}(x),G_{n}^{*}(x))=\gcd(G_{m_1}^{*}(x),G_{0}^{*}(x))=\gcd(G_{d}^{*}(x),G_{0}^{*}(x))$.

Now suppose that $m_1 \nmid m$. Therefore there are two non-negative integers $r_2$ and $q_2$ such that $m=m_1q_2+r_2$ where $0<r_2<m_1$. From Lemma \[fundamental\] we guarantee that we can find $m_2$ such that $m_2<m_1$, $\gcd(m_1,m_2)=d$ and $\gcd(G_{m_1}^{*}(x),G_{m_2}^{*}(x))=\gcd(G_{m_1}^{*}(x),G_{m}^{*}(x))$. In this form we construct a set $M_t= \{n, m, m_1, m_2, \ldots, m_t\}$ where $n> m>m_1>\cdots >m_t$ such that $\gcd(m_j,m_{j-1})=d$ and $$\gcd(G_{n}^{*}(x),G_{m}^{*}(x))=\gcd(G_{m_1}^{*}(x),G_{m}^{*}(x))=\cdots=
\gcd(G_{m_j}^{*}(x),G_{m_{j-1}}^{*}(x)).$$ From Lemma \[fundamental\] we know that $n> m>m_1>\cdots >m_j$ ends only if $r_j=0$. Since $M_j= \{n, m, m_1, m_2, \ldots, m_j\}$ is an ordered sequence of natural numbers, it has a minimum element $m_j$.

Therefore, $m_{j}\mid m_{j-1}$. It is easy to see that $
\gcd(G_{n}^{*}(x),G_{m}^{*}(x))=\gcd(G_{m_j}^{*}(x),G_{m_{j-1}}^{*}(x))$. This is equivalent to $\gcd(G_{n}^{*}(x),G_{m}^{*}(x))=\gcd(G_{d}^{*}(x),G_{0}^{*}(x)).
$ This completes the proof.

Let $d_{k}=\gcd(G_0 ^*(x),G_{k} ^{*}(x))$ where $G_{k}^{*}(x)$ is GFP of the Lucas type. If $m$ and $n$ are positive integers such that $E_{2}(n)\ne E_{2}(n)$, then

(1) Suppose that there is an integer $k'>0$ such that $d_{k'}=2$. If $r$ is the minimum positive integer such that $d_{r}=2$, then $$\gcd(G_{m}^{*}(x),G_{n}^{*}(x))= \begin{cases} 2 & \mbox{ if }\;   r|\gcd(m,n);\\
                                                        1   & \mbox{ otherwise}.
                                            \end{cases}$$

(2) If $d_{k}\ne 2$ for every positive integer $k$, then $\gcd(G_{m}^{*}(x),G_{n}^{*}(x))=1$.

It straightforward from Proposition (\[propiedadDivisioncase2\]).

\[gcd:fibonaccilucas:samegcdlucaslucas\] Let $\{ G_{n}^{*}(x)\}$ and $\{ G_{n}^{'}(x)\}$ be equivalent GFP. If $m$ and $n$ are positive integers, then

(1) $\gcd(G^{'}_{m+n+1}(x),G_{n}^{*}(x))=\gcd(G_{m+1}^{*}(x),G_{n}^{*}(x)),$

(2) if $m>n$, then $\gcd(G^{'}_{m-n+1}(x),G_{n}^{*}(x))=\gcd(G_{m+1}^{*}(x),G_{n}^{*}(x)),$

(3) if $m<n$, then $\gcd(G^{'}_{n-m+1}(x),G_{n}^{*}(x))=\gcd(G_{m-1}^{*}(x),G_{n}^{*}(x)).$

We first prove part (1) by induction. Let $S(n)$ be the statement (recall that $a-b=a(x)-b(x)$): for every $n\ge 1$ $\gcd((a-b)^2,G_{n}^{*}(x))=1$. Recall that in a GFP of Lucas type holds that $\gcd(p_0(x), p_1(x))=\gcd(p_0(x), d(x))=1$ and that $2p_1(x)=p_0(x)d_(x)$. From this and using Proposition \[divisity:Hogat:property2\] part (1) with $m=n=0$, it is easy to see that $\gcd((a-b)^2,G_{1}^{*}(x))=1$. We now prove that $S(2)$ is also true. It is easy to see that $$\begin{aligned}
\gcd((a-b)^2,G_{2}^{*}(x))&=&\gcd(a^2(x)+b^2(x)-2ab,G_2^{*}(x))\\
&=&\gcd(G_{2}^{*}(x)+2g(x),G_{2}^{*}(x))\\
&=&\gcd(2g(x),G_{2}^{*}(x)).\end{aligned}$$

From Lemma (\[gcdlemmas\]) part (3) we know that $\gcd(g(x),G_{2}^{*}(x))=1$. This implies that either $$\gcd((a-b)^2,G_{2}^{*}(x))=1 \; \text{ or } \; \gcd((a-b)^2,G_{2}^{*}(x))=2.$$ If $\gcd((a-b)^2,G_{2}^{*}(x))=2$, then $2\mid \left(d^2(x)+4g(x)\right)$ and $2\mid G_{2}^{*}(x)$. So, $2\mid d^2(x)$ and $2\mid G_{2}^{*}(x)$. From Lemma (\[gcdlemmas\]) part (2) we know that $\gcd(d(x),G_{2}^{*}(x))=1$. This implies that $2 \mid 1$. Therefore, $\gcd((a-b)^2,G_{2}^{*}(x))=1$. This proves $S(2)$.

Suppose that that $S(n)$ is true for some $k$. Thus, suppose that $\gcd((a-b)^2,G_{k}^{*}(x))=1$. We prove that $S(k+1)$ is true. Suppose that $\gcd((a-b)^2,G_{k+1}^{*}(x))=r(x)$. Therefore, $r(x)\mid(a-b)^2$ and $r(x)\mid G_{k+1}^{*}(x)$. So, $r(x) \mid [(a-b)^2G^{'} _{2k+1}(x)-\alpha^2(G^*_{k+1}(x))^2]$. From Proposition \[divisity:Hogat:property2\] part (1) we know that if $m=n=k$, then $$(a-b)^2G^{'} _{k+k+1}(x)=\alpha^2 G_{k+1}^{*}(x)G_{k+1}^{*}(x)+\alpha^2g(x)G_{k}^{*}(x)G_{k}^{*}(x).$$ Thus, $
(a-b)^2G^{'} _{2k+1}(x)-\alpha^2(G^{*}_{k+1}(x))^2=\alpha^2g(x)(G^{*}_k (x))^2.
$ This implies that $r(x)$ divides $ \alpha^2 g(x)(G^{*} _k(x))^2$. Since $|\alpha| = 1$ or $2$, from the definition of GFP and Proposition \[gcddistance1;2\] is easy to see that $\gcd(\alpha,g(x))=1$. We know that $\gcd(\alpha, G_n)=1$ for every $n$. So, $\gcd(\alpha, r(x))=1$. We recall that from Lemma (\[gcdlemmas\]) part (3), that $\gcd(g(x),G_{k+1}^{*}(x))=1$. This and $r(x)\mid G_{k+1}^{*}(x)$ imply that $\gcd(r(x),g(x))=1$. Now it is easy to see that $r(x)\mid (G^{*} _{k}(x))^2$. Since $r(x)\mid (a-b)^2$ and $\gcd((a-b)^2,G_{k}^{*}(x))=1$, we have that $r(x)=1$. This proves that $S(k+1)$ is true. That is, $\gcd((a-b)^2,G_{n}^{*}(x))=1$.

We now prove that $\gcd(G^{'}_{m+n+1}(x),G_{n}^{*}(x))=\gcd(G_{m+1}^{*}(x),G_{n}^{*}(x)).$ Proposition \[divisity:Hogat:property2\] part (1), implies that $$\begin{aligned}
\gcd((a-b)^2G^{'}_{m+n+1}(x),G_{n}^{*}(x))&=&\gcd(\alpha^{2}G_{m+1}^{*}(x)G_{n+1}^{*}(x)+\alpha^{2}g(x)G_{m}^{*}(x)G_{n}^{*}(x),G_{n}^{*}(x))\\
                           &=&\gcd(\alpha^{2} G_{m+1}^{*}(x)G_{n+1}^{*}(x),G_{n}^{*}(x)).\end{aligned}$$ From Proposition \[gcddistance1;2\] and $\gcd (\alpha, G_{n+1})=1$ we know that $\gcd(\alpha^{2} G_{n+1}^{*}(x),G_{n}^{*}(x))=1$. Therefore, by Proposition \[prop2;1\] part (2) we have $\gcd(G_{m+1}^{*}(x)G_{n+1}^{*}(x),G_{n}^{*}(x))=\gcd(G_{m+1}^{*}(x),G_{n}^{*}(x))$. This implies that $$\gcd((a-b)^2G^{'}_{m+n+1}(x),G_{n}^{*}(x))=\gcd(G_{m+1}^{*}(x),G_{n}^{*}(x)).$$ This and $\gcd((a-b)^2,G_{n}^{*}(x))=1$ imply that $$\gcd(G^{'}_{m+n+1}(x),G_{n}^{*}(x))=\gcd(G_{m+1}^{*}(x),G_{n}^{*}(x)).$$

Proof of part (2). From Lemma \[gcdlemmas\] part (3) it is easy to see that $\gcd(G_{m-n+1}^{'}(x), G_{n}^{*}(x))$ is equal to $\gcd((g(x))^n G_{m+1-n}^{'}(x), G_{n}^{*}(x))$. This and Proposition \[divisity:Hogat:property1\] part (2) (after interchanging the roles of $m$ and $n$), imply that $\gcd(G_{m-n+1}^{'}(x), G_{n}^{*}(x))$ equals $$\gcd(\alpha G_{m+1}^{'}(x)G_{n}^{*}(x)-G_{m+1+n}^{'}(x),G_{n}^{*}(x))=\gcd(G_{m+n+1}^{'}(x), G_{n}^{*}(x)).$$ The conclusion follows from part (1).

Proof of part (3). From Lemma \[gcdlemmas\] part (3) it is easy to see that $$\gcd(G_{n-m+1}^{'}(x), G_{n}^{*}(x)) =\gcd((-g(x))^{m-1} G_{n-(m-1)}^{'}(x), G_{n}^{*}(x)).$$ This and Proposition \[divisity:Hogat:property1\] part (3), imply that $\gcd(G_{m-n+1}^{'}(x), G_{n}^{*}(x))$ equals $$\gcd(G_{n+m-1}^{'}(x)-\alpha G_{m-1}^{'}(x)G_{n}^{*}(x),G_{n}^{*}(x))=\gcd(G_{n+(m-2)+1}^{'}(x), G_{n}^{*}(x)).$$ The conclusion follows from part (1).

\[combine:gcd:Lucas:Fibobacci\] Let $\{ G_{n}^{*}(x)\}$ and $\{ G_{n}^{'}(x)\}$ be equivalent GFP. If $m$ and $n$ are positive integers and $\gcd(m,n)=d$, then $$\gcd(G^{'}_{m}(x),G_{n}^{*}(x))= \begin{cases}
                                             G_{d}^{*}(x) & \mbox{ if } E_2(m)>E_2(n); \\
                                                     \gcd(G_{ d }^{*}(x),G_{0}^{*}(x))  & \mbox{ otherwise.  }

                               \end{cases}$$

We suppose that $E_2(m)>E_2(n)$. We prove this part of the Theorem by cases.

[**Case**]{} $m>n$. Since $m>n$, there is a positive integer $l$ such that $m=n+l$. Therefore, $\gcd(G^{'}_{m}(x),G_{n}^{*}(x))=\gcd(G^{'}_{l-1+n+1}(x),G_{n}^{*}(x))$. This and Proposition \[gcd:fibonaccilucas:samegcdlucaslucas\] part (1) imply that $\gcd(G^{'}_{m}(x),G_{n}^{*}(x))=\gcd(G_{l}^{*}(x),G_{n}^{*}(x))$. Since $E_2(m)>E_2(n)$ and $m=n+l$, we have that $E_2(l)=E_2(n)$. This and Theorem \[second:main:thm\] imply that $\gcd(G_{l}^{*}(x),G_{n}^{*}(x))=G_{\gcd(l,n)}^{*}(x)$. From Lemma \[Dic1\] it is easy to see that $\gcd(l,n)=\gcd(m,n)$. Thus, $\gcd(G_{l}^{*}(x),G_{n}^{*}(x))=G_{\gcd(m,n)}^{*}(x)$. So, $\gcd(G^{'}_{m}(x),G_{n}^{*}(x))=G_{\gcd(m,n)}^{*}(x)$.

[**Case**]{} $m<n$. The proof of this case is similar to the proof of Case $m>n$. It is enough to replace $m$ by $n-(l+1)$ in $\gcd(G^{'}_{m}(x),G_{n}^{*}(x))$, and then use Proposition \[gcd:fibonaccilucas:samegcdlucaslucas\] part (3).

We now suppose that $E_2(m)\le E_2(n)$. We prove this part of the Theorem by cases.

[**Case**]{} $m>n$. So, there is a positive integer $l$ such that $m= l+n$. Therefore by Proposition \[gcd:fibonaccilucas:samegcdlucaslucas\] part (1) we have $$\gcd(G^{'}_{m}(x),G_{n}^{*}(x))=\gcd(G^{'}_{n+(l-1)+1}(x),G_{n}^{*}(x))=\gcd(G_{l}^{*}(x),G_{n}^{*}(x)).$$ Note that if $m=n+l$ and $E_2(m)\le E_2(n)$, then there are integers $k_1$, $k_2$, $q_1$ and $q_2$ with $k_1\leq k_2$ such that $m=2^{k_1} q_1$ and $n=2^{k_2} q_2$. Since $m=n+l$, we see that $E_2(l)\neq  E_2(n)$. This and Theorem \[second:main:thm\] imply that $\gcd(G_{l}^{*}(x),G_{n}^{*}(x))=\gcd(G_{0}^{*}(x),G_{\gcd(n,l)}^{*}(x))$. Thus, $\gcd(G^{'}_{m}(x),G_{n}^{*}(x))=\gcd(G_{0}^{*}(x),G_{\gcd(m,n)}^{*}(x))$.

[**Case**]{} $m<n$. The proof of this case is similar to the proof of Case $m>n$. It is enough to replace $m$ by $n-(l+1)+1$ in $\gcd(G^{'}_{m}(x),G_{n}^{*}(x))$, and then use Proposition \[gcd:fibonaccilucas:samegcdlucaslucas\] part (3).

[**Case**]{} $m=n$. Since $n=(2n-1)-n+1$, taking $m=2n-1$ in Proposition \[gcd:fibonaccilucas:samegcdlucaslucas\] part (2) and using Theorem \[second:main:thm\] we obtain that $$\gcd(G'_{n}(x),G^{*} _{n}(x))=\gcd(G'_{(2n-1)-n+1}(x),G^{*} _{n}(x))=\gcd(G^{*} _{2n}(x),G^{*} _n(x))=\gcd(G_{0}^{*}(x),G_{n}^{*}(x)).$$ This completes the proof.

Hoggatt and Bicknell-Johnson [@hoggatt Thm. 3.4] proved that Fibonacci polynomials, Chebyshev polynomials of second kind, Morgan-Voyce polynomial, and Schechter polynomial satisfy the strong divisibility property. Theorem \[gcd:property:fibonacci\] proves the necessary and sufficient condition for the polynomials in a generalized Fibonacci polynomial sequence to satisfy the strong divisibility property. Norfleet [@norfleet] also prove the some strong divisibility property for GFP of Fibonacci type.

\[gcd:property:fibonacci\] Let $\{ G_{k}(x)\}$ be a GFP of either Fibonacci type or Lucas type. For any two positive integers $m$ and $n$ it holds that $\gcd(G_{m}(x),G_{n}(x))=G_{\gcd(m,n)}(x)$ if and only if $\{ G_{k}(x)\}$ is a sequence of GFP of the Fibonacci type.

Let $\{ G_{n}^{'}(x)\}$ be a generalized Fibonacci polynomial sequence of the Fibonacci type, we now show that $\gcd(G_{m}^{'}(x),G_{n}^{'}(x))$ divides $G_{\gcd(m,n)}^{'}(x)$ for $m>0$, $n>0$ and vice versa.

If $G_{n}^{'}$ is of Fibonacci type, by Proposition \[divisity:property:fibonacci\], it is clear that $G_{\gcd(m,n)}^{'} \mid \gcd(G_{m}^{'}(x),G_{n}^{'}(x))$. Next we show that $\gcd(G_{m}^{'}(x),G_{n}^{'}(x))$ divides $G_{\gcd(m,n)}^{'}$.

Let $k=\gcd(m,n)$ and suppose without lost of generality that $k$ is neither equal $n$ nor equal $m$. The Bézout identity implies that there are two positive integers $r$ and $s$ such that $k=rm-sn$. So, $rm=k+sn$ and $G_{rm}^{'}(x) =G_{k+sn}^{'}(x)$ This, Proposition \[divisity:Hogat:property1\] part (1), and the fact that $k+sn=(k+(sn-1))+1$, imply that $$G_{rm}^{'}(x)= G_{k+1}^{'}(x)G_{s'n}^{'}(x)+g(x)G_{k}^{'}(x)G_{sn-1}^{'}(x).$$

We note that, by Proposition \[divisity:property:fibonacci\], $G_{m}^{'}(x)$ divides $G_{rm}^{'}(x)$ and $G_{n}^{'}(x)$ divides $G_{sn}^{'}(x)$. Since $\gcd(G_{m}^{'}(x),G_{n}^{'}(x)) \mid G_{m}^{'}(x)$ and $\gcd(G_{m}^{'}(x),G_{n}^{'}(x)) \mid G_{n}^{'}(x)$, and $G_{m}^{'}(x)\mid G_{rm}^{'}(x)$ and $G_{n}^{'}(x)\mid G_{s'n}^{'}(x)$, we have that $\gcd(G_{m}^{'}(x),G_{n}^{'}(x))$ divides $G_{rm}^{'}(x)$ and $G_{s'n}^{'}(x)$. This together with Lemma \[gcdlemmas\] part (3) and the fact that $\gcd(G_{m}^{'}(x),G_{n}^{'}(x))$ does not divide $G_{s'n-1}^{'}(x)$, implies that $\gcd(G_{m}^{'}(x),G_{n}^{'}(x))$ divides $G_{k}^{'}(x)$.

Conversely, suppose that $\{ G_{n}(x)\}$ is a generalized Fibonacci polynomial sequence such that the strong divisibility property holds, or $\gcd(G_{m}(x),G_{n}(x))=G_{\gcd(m,n)}(x)$ for any two positive integers $m$ and $n$, we now show that both $G_{m}(x)$ and $G_{n}(x)$ are GFP of the Fibonacci type. We prove this using the method of contradiction.

If $G_{m}(x)$ and $G_{n}(x)$ are in $\{ G_{n}(x)\}$ such that they are both GFP of the Lucas type, then by Theorem \[second:main:thm\] we obtain a contradiction. This completes the proof.

The gcd properties of Familiar GFP and questions
================================================

In this section we formulate a general question and present three tables which are corollaries of the main results in Section \[gcd:characterization\]. These tables give us the strong divisibility property of the familiar polynomials which satisfy the Binet formulas (\[bineformulados\]) and (\[bineformulauno\]). Table \[corollary\_Fibonacci\] gives the gcd’s for Fibonacci polynomials, Pell polynomials, Fermat polynomials, Jacobsthal polynomials, Chebyshev’s second kind polynomials and one type of Morgan-Voyce $B_n$ polynomials. Table \[corollary\_lucas\] gives the strong divisibility property of the Lucas polynomials, Pell-Lucas polynomials, Fermat-Lucas polynomials, Jacobsthal-Lucas polynomials, Chebyshev’s first kind polynomials and Morgan-Voyce $C_n$ polynomials, while Table \[corollary\_lucas\_2\] gives the $\gcd$ of a polynomial of the Lucas type and its equivalent.

We should note here that in the case of Table \[corollary\_lucas\], the strong divisibility property is partially satisfied since it only holds when the largest powers of 2 that divides $m$ and the largest powers of 2 that divides $n$ are both equal. (That is, $E_{2}(m)= E_{2}(n)$.) Similarly the strong divisibility property only holds in Table \[corollary\_lucas\_2\] when $E_{2}(n)<E_{2}(m)$.

\[!ht\]

\[!ht\]

\[!ht\]

Questions
---------

1.  Let $\{G_{n}^{*}(x)\}$ and $\{ S_{n}(x)\}$ be generalized Fibonacci polynomial sequences of Lucas type and Fibonacci type, respectively. If $S_{n}(x) $ is not the equivalent of $G_{n}^{*}(x)$, what is the $\gcd(G_{k}^{*}(x),S_{m}(x))$? We believe that the answer is: $1$ or $x$.

2.  Let $\{G_{n}(x)\}$ and $\{S_{n}(x)\}$ be two different Fibonacci polynomial sequences of the same type, then do they satisfy the strong divisibility property?

3.  ([**Conjecture.**]{}) The GFP $T_{n}$ and $S_{m}$ satisfy the strong divisibility property if and only if $T_{n}$ and $S_{m}$ are both of Fibonacci type and they belong to the same generalized Fibonacci polynomial sequence. Theorems \[combine:gcd:Lucas:Fibobacci\] and \[gcd:property:fibonacci\] are evidence that the conjecture is true.

4.  Let $\mathcal{R}$ be a set of recursive functions. If $\mathcal{F}  :  \mathbb{N}  \to \mathcal{R}$, $\mathcal{G} :  \mathcal{R} \times \mathcal{R} \to \mathcal{R}$ and $g: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$, under what conditions $\mathcal{G} \circ  (\mathcal{F} \times \mathcal{F} )= \mathcal{F} \circ g$ for all $\mathcal{F}\in \mathcal{R}$ and a fix $g$?

Acknowledgement
===============

The first and last authors were partially supported by The Citadel Foundation.

[99]{}

R. André-Jeannin, Differential properties of a general class of polynomials, *Fibonacci Quart.* **33** (1995), 453–458.

R. André-Jeannin, A generalization of Morgan-Voyce polynomials, *Fibonacci Quart.* **32** (1994), 228–231.

R. Flórez, R. Higuita and A. Mukherjee, Alternating sums in the Hosoya polynomial triangle, *J. Integer Seq.*, **17** (2014), Article 14.9.5.

R. Flórez, R. Higuita and L. Junes, 9-modularity and gcd properties of generalized Fibonacci numbers, *Integers*, **14** (2014), Paper No. A55, 14pp.

R. Flórez and L. Junes, gcd properties in Hosoya’s triangle, *Fibonacci Quart.* **50** (2012), 163–174.

M. Hall, Divisibility Sequences of Third Order, *Amer. J. Math.* **58** (1936), 577-584.

R. T. Hansen, Generating Identities for Fibonacci and Lucas Triples , *Fibonacci Quart.* **10** (1972), 571–578.

P. Hilton, P. J. Pedersen, and L. Vrancken, On certain arithmetic properties of Fibonacci and Lucas numbers, *Fibonacci Quart.* **3** (1995), 211–217.

V. E. Hoggatt,  Jr., and C. T. Long, Divisibility properties of generalized Fibonacci polynomials, *Fibonacci Quart.* **12** (1974), 113–120.

V. E. Hoggatt,  Jr., and M. Bicknell-Johnson, Divisibility properties of polynomials in Pascal’s triangle, *Fibonacci Quart.* **16** (1978), 501–513.

A. F. Horadam, A synthesis of certain polynomial sequences, *Applications of Fibonacci numbers*, Vol. 6 (Pullman, WA, 1994), 215–229, Kluwer Acad. Publ., Dordrecht, 1996.

C. Kimberling, , Greatest common divisors of sums and differences of Fibonacci, Lucas, and Chebyshev polynomials, *Fibonacci Quart.* **17** (1979), 18–22.

C. Kimberling, Strong divisibility sequences and some conjectures, *Fibonacci Quart.* **17** (1979), 13–17.

C. Kimberling, Strong divisibility sequences with nonzero initial term, *Fibonacci Quart.* **16** (1978), 541–544.

E. Lucas, Théorie des fonctions numériques simplement périodiques, *Amer. J. Math.* 1 (1878), 184-240, 289-321.

A. F. Horadam and J. M. Mahon, Pell and Pell-Lucas polynomials, *Fibonacci Quart.* **23** (1985), 7–20.

A. F. Horadam, Chebyshev and Fermat polynomials for diagonal functions, *Fibonacci Quart.* **17** (1979), 328–333.

T. Koshy, *Fibonacci and Lucas Numbers with Applications*, John Wiley, New York, 2001.

J. Lahr, Fibonacci and Lucas numbers and the Morgan-Voyce polynomials in ladder networks and in electric line theory, *Fibonacci numbers and their applications*, (Patras, 1984), 141–161.

W. McDaniel, The g.c.d. in Lucas sequences and Lehmer number sequences, *Fibonacci Quart.* **29** (1991), 24–29.

A. M. Morgan-Voyce, Ladder network analysis using Fibonacci numbers, *IRE Trans. Circuit Th.* **CT-6** (1959), 321–322.

M. Norfleet, Characterization of second-order strong divisibility sequences of polynomials, *Fibonacci Quart.* **43** (2005), 166–169.

M. O. Rayes, V. Trevisan, and P. S. Wang, Factorization properties of Chebyshev polynomials, *Comput. Math. Appl.* **50** (2005), 1231–1240.

M. N. S. Swamy, Properties of the polynomials defined by Morgan-Voyce, *Fibonacci Quart.* **4** (1966a), 73–81.

M. Ward, Note on divisibility sequences, *Bull. Amer. Math. Soc.* **42** (1936), 843-845.

W. A. Webb and E. A. Parberry, Divisibility properties of Fibonacci polynomials, *Fibonacci Quart.* **7** (1969), 457–463.

------------------------------------------------------------------------

MSC 2010: Primary 11B39; Secondary 11B83.

*Keywords:* Greatest common divisor, strong divisibility property, generalized Fibonacci polynomial, Fibonacci polynomial, Lucas polynomial.
