Generalization of Jarden’s Theorem

E. L. Roettger Department of General Education Mount Royal University 4825 Mount Royal Gate SW Calgary, AB T3E 6K6 Canada

                 eroettger@mtroyal.ca

H. C. Williams Department of Mathematics and Statistics University of Calgary 2500 University Drive NW Calgary, AB T2N 1N4 Canada

                 hwilliam@ucalgary.ca

Abstract

Let (F_{n})_{n≥0} and (L_{n})_{n≥0} denote the sequences of Fibonacci numbers and Lucas numbers, respectively. In 1950 Dov Jarden showed that if m = 5 and n is odd and positive, then

L_{mn}/L_{n} = A_{n}B_{n},

where

A_{n} = 5F_{n}^{2} − 5F_{n} + 1, B_{n} = 5F_{n}^{2} + 5F_{n} + 1.

He went on to show that if n and k are both odd and positive and η is the value of the Legendre symbol (k|5), then A_{n} | A_{kn}, B_{n} | B_{kn} when η = 1 and A_{n} | B_{kn}, B_{n} | A_{kn} when η = −1. In this paper we show how to generalize these results for values of m which are odd and square-free to the Lucas sequence (V_{n})_{n≥0}.

1 Introduction

Let P, Q be integers and α, β denote the zeros of f(x) = x^{2} − P x + Q. We will use D (= P^{2} − 4Q) to represent the discriminant (α − β)^{2} of f(x). Let

U_{n} = (α^{n} − β^{n})/(α − β) and V_{n} = α^{n} + β^{n}.  (1)

For n ≥ 0, it is easy to see that both U_{n} and V_{n} are integers. The sequences (U_{n}) and (V_{n}) are called the Lucas sequences. For example, if we put P = 1, Q = −1, then U_{n} = F_{n} and V_{n} = L_{n}, where (F_{n}) is the sequence of Fibonacci numbers and (L_{n}) is the sequence of Lucas numbers. In the sequel we will use n to denote a positive integer.

In a short paper originally published in Hebrew in 1950, Dov Jarden (see [8, §8] for an English version) verified by using (1) the identity

L_{5n}/L_{n} = A_{n}B_{n},  (2)

where n is odd and

A_{n} = 5F_{n}^{2} − 5F_{n} + 1, B_{n} = 5F_{n}^{2} + 5F_{n} + 1.

This rather pretty identity does not seem to be very well known. Since

L_{n}^{2} − 5F_{n}^{2} = 4(−1)^{n},

we can write

A_{n} = L_{n}^{2} − 5F_{n} + 5, B_{n} = L_{n}^{2} + 5F_{n} + 5.

Let k be any odd positive integer. Most of Jarden’s paper is devoted to proving the following result.

Theorem 1. Let n, k denote odd positive integers. We have

A_{n} | A_{kn} and B_{n} | B_{kn} when k ≡ 1, 4 (mod 5).

Also,

A_{n} | B_{kn} and B_{n} | A_{kn} when k ≡ 2, 3 (mod 5).

This result was called a crossover theorem by Brillhart, Montgomery, and Silverman [2] and was enlisted by them to assist in compiling a table of integer factorizations of the Lucas numbers.

The purpose of this paper is to generalize Jarden’s crossover theorem. In order to do this we will require some results from the theory of what today are called Aurifeuillians. We begin by defining the cyclotomic polynomial Φ_{m}(x) ∈ ℤ[x] to be

Φ_{m}(x) = ∏(x − ζ_{m}^{s}),

where ζ_{m} is a primitive m^{th} root of unity and the product is taken over all values s between 0 and m and relatively prime to m. It is well known that we can write Φ_{m}(x) as

Φ_{m}(x) = ∏_{d|m}(x^{d} − 1)^{μ(m/d)},  (3)

where μ is the Möbius function. Lucas [5, 6], observed that certain formulas for Φ_{m}(x), which he attributed to Aurifeuille and Le Lasseur, could be used to derive identities involving the Lucas sequences and for factoring some of these expressions. For example, in [6, p. 172] he gave the identity

V_{10n}/V_{2n} = (V_{4n} + 5Q^{n}V_{2n} + 7Q^{2n})^{2} − 10Q^{n}(V_{2n} + 2Q^{n}V_{n})^{2}.

He derived this from the Aurifeuillian formula

Φ_{20}(x) = \frac{x^{10} + 1}{x^{2} + 1} = (x^{4} + 5x^{3} + 7x^{2} + 5x + 1)^{2} − 10x(x^{3} + 2x^{2} + 2x + 1)^{2},

by putting x = α^{n}/β^{n}. Notice that this expression for V_{10n}/V_{2n} will factor as a difference of squares when 10Q^{n} is a perfect integral square. This means that Q = 10L^{2}, where L is an integer.

Other results, apparently unknown to Lucas, can be obtained by substituting other expressions involving α^{n}/β^{n} for x in Aurifeuillian formulas. As an example, consider

Φ_{5}(x) = \frac{x^{5} − 1}{x − 1} = (x^{2} + 3x + 1)^{2} − 5x(x + 1)^{2},

a formula known to Lucas [6, p. 168]. If we put x = (−α^{n}/β^{n})^{1/2}, we get

V_{5n}/V_{n} = (V_{n}^{2} − 5Q^{n})^{2} + 5Q^{n}DU_{n}^{2} = (DU_{n}^{2} − Q^{n})^{2} + 5Q^{n}DU_{n}^{2}.

If −5Q^{n}D is a perfect integral square we can find a factorization of V_{5n}/V_{n}. When we consider the special case of P = 1, Q = −1, we have −5Q^{n}D = 25 when n is odd and we get (2).

For recent information concerning Aurifeuillians and additional references the reader is advised to consult Granville and Pleasants [7] and Wagstaff [12, §4.1]. For some historical commentary, see Williams [13, pp. 126–127, pp. 318–319].

2 Preliminary results

Let m (> 3) be a fixed square-free positive odd integer. Put σ = (−1)^{\frac{m−1}{2}} and m^{∗} = σm ≡ 1 (mod 4). For a real number r, we will use \sqrt{r} to denote the positive square root of r when r ≥ 0 or i\sqrt{|r|} when r < 0. Next, set

S_{m} = {s : 1 ≤ s < m; gcd(m, s) = 1}.

By the definition of ϕ(m), we have

#S_{m} = ϕ(m).

Now let ϵ ∈ {1, −1} and put S_{m}^{(ϵ)} = {s : 1 ≤ s < m; (s|m) = ϵ} for a fixed ϵ. As there are just as many values of s ∈ S_{m} such that (s|m) = 1 and that (s|m) = −1, we see that

#S_{m}^{(ϵ)} = #S_{m}^{(−ϵ)} = ϕ(m)/2.

Also, note that for any s ∈ S_{m}, we also have m − s ∈ S_{m}. Thus, S_{m} consists of ϕ(m)/2 pairs (s, m − s). It follows that since s + m − s = m, we get

∑_{s∈S_{m}} s = mϕ(m)/2.

If we put

Σ_{m}^{(ϵ)} = ∑_{s∈S_{m}^{(ϵ)}} s,

we have

Σ_{m}^{(ϵ)} + Σ_{m}^{(−ϵ)} = mϕ(m)/2.

Since m > 3, there must exist some integer r such that the Jacobi symbol (r|m) = −1 and gcd(r + 1, m) = 1. Thus, we get

rΣ_{m}^{(ϵ)} ≡ ∑_{s∈S_{m}^{(ϵ)}} rs ≡ ∑_{s∈S_{m}^{(−ϵ)}} s = Σ_{m}^{(−ϵ)} (mod m).

Since m | Σ_{m}^{(ϵ)} + Σ_{m}^{(−ϵ)}, we get

(r + 1)Σ_{m}^{(ϵ)} ≡ 0 (mod m)

which means that

Σ_{m}^{(ϵ)} ≡ Σ_{m}^{(−ϵ)} ≡ 0 (mod m).  (4)

Also, since (rs|m) = −(s|m), we find that

∑_{s∈S_{m}}(s|m) = − ∑_{s∈S_{m}}(s|m);

hence,

∑_{s∈S_{m}}(s|m) = 0.  (5)

Let I be a given integral domain and let p(x) ∈ I[x] be the polynomial

p(x) = a_{0}x^{n} + a_{1}x^{n−1} + ⋯ + a_{n−1}x + a_{n},

where a_{j} ∈ I (j = 0, 1, …, n). If p(x) = p(−x), then a_{j} = 0 whenever 2 ∤ j; also, if p(x) = −p(−x), then a_{j} = 0 whenever 2 | j. We say that p(x) is palindromic of order n over I if

a_{j} = a_{n−j} (j = 0, 1, 2, …, n),

and that p(x) is antipalindromic of order n if

a_{j} = −a_{n−j} (j = 0, 1, 2, …, n).

When I = ℤ, we will omit including I and simply say that p(x) is palindromic or antipalindromic. Notice that under this definition the polynomial x = (0x^{2} + x + 0) is palindromic of order 2 over I. Also, if p(x) is antipalindromic of degree n, where 2 | n, then a_{n/2} = 0.

The next results follow easily from the above observations and definitions. We first let p(x) denote a polynomial over I which is either palindromic or antipalindromic of order n and define q(x) = p(−x).

i) If 2 | n, then q(x) is either palindromic or antipalindromic of order n over I, according to whether p(x) is palindromic or antipalindromic.

ii) If 2 ∤ n, then q(x) is antipalindromic or palindromic of order n over I, according to whether p(x) is palindromic or antipalindromic.

iii) If 2 | n and p(x) = q(x), then p(x) = r(x^{2}), where r(x) is a palindromic or antipalindromic polynomial over I of order n/2, according to whether p(x) is palindromic or antipalindromic.

iv) If 2 | n and p(x) = −q(x), then p(x)/x = r(x^{2}), where r(x) is a palindromic or antipalindromic polynomial over I of order n/2 − 1, according to whether p(x) is palindromic or antipalindromic.

Proposition 2. p(x) is palindromic of order n over I if and only if

p(x) = x^{n}p(1/x)

and p(x) is antipalindromic of order n over I if and only if

p(x) = −x^{n}p(1/x).

From this result, we can easily derive the following:

v) If c_{1}, c_{2} ∈ I and p_{1}(x), p_{2}(x) are both either palindromic or antipalindromic polyno-

mials of order n over I, then

c_{1}p_{1}(x) + c_{2}p_{2}(x)

is a palindromic or antipalindromic polynomial of order n over I according to whether p_{1}(x) and p_{2}(x) are palindromic or antipalindromic. vi) If p_{1}(x) and p_{2}(x) are both palindromic or antipalindromic polynomials of order n_{1}

and n_{2}, respectively, over I, then

p_{1}(x)p_{2}(x)

is a palindromic polynomial of order n_{1} + n_{2} over I.

vii) If p_{1} is a palindromic polynomial of degree n_{1} and p_{2} is an antipalindromic polynomial

of degree n_{2}, then

p_{1}(x)p_{2}(x)

is an antipalindromic polynomial of order n_{1} + n_{2} over I.

3 Some Aurifeuillian identities

We now let ζ_{h} denote any fixed primitive h^{th} root of unity. Define for m above

A_{m}^{(ϵ)}(x) = ∏_{s∈S_{m}^{(ϵ)}}(x − ζ_{m}^{s}).  (6)

Set e = ϕ(m)/2 and observe that if σ = 1, then 2 | e. By results of Gauss and Dirichlet (see [3]), we know that A_{m}^{(ϵ)}(x) is a polynomial of degree e over O, the maximal order of the quadratic field ℚ(\sqrt{m^{∗}}). Indeed

A_{m}^{(ϵ)}(x) = \frac{1}{2}(Y_{m}(x) − ϵ\sqrt{m^{∗}}Z_{m}(x)),

where Y_{m}(x), Z_{m}(x) ∈ ℤ[x] and Y_{m}(x) ≡ Z_{m}(x) (mod 2). Also, by using (4) we can show that we have

A_{m}^{(ϵ)}(x) = x^{e}A_{m}^{(ϵ)}(1/x)

when m ≡ 1 (mod 4) and

A_{m}^{(ϵ)}(x) = (−x)^{e}A_{m}^{(−ϵ)}(1/x)

when m ≡ −1 (mod 4). Hence,

Y_{m}(x) = x^{e}Y_{m}(1/x), Z_{m}(x) = x^{e}Z_{m}(1/x)

when m ≡ 1 (mod 4) and

Y_{m}(x) = (−x)^{e}Y_{m}(1/x), −Z_{m}(x) = (−x)^{e}Z_{m}(1/x)

when m ≡ −1 (mod 4). By using Proposition 2 we can summarize the palindromicantipalindromic properties of Y_{m}(x), Z_{m}(x) in Table 1.

m (mod 4) e (mod 2)  Y_{m}(x)  Z_{m}(x)
1  0  palindromic of order e  palindromic of order e
−1  0  palindromic of order e antipalindromic of order e
−1  1  antipalindromic of order e palindromic of order e

Table 1: Palindromic-antipalindromic properties of Y_{m}(x), Z_{m}(x). Put

L_{m}^{(ϵ)}(x) = A_{m}^{(ϵ)}(x)A_{m}^{(−ϵ)}(−x),  (7)
= G_{m}(x) − ϵx\sqrt{m^{∗}}H_{m}(x),

where

G_{m}(x) = \frac{1}{4}(Y_{m}(x)Y_{m}(−x) − m^{∗}Z_{m}(x)Z_{m}(−x)),
H_{m}(x) = \frac{1}{4}(Y_{m}(−x)Z_{m}(x) − Y_{m}(x)Z_{m}(−x)).

Notice that because Y_{m}(x) ≡ Z_{m}(x) (mod 2), we have G_{m}(x), H_{m}(x) both polynomials over ℤ. By appealing to Table 1 and Properties v), vi), vii) of Section 2, we can produce Table 2.

m (mod 4) e (mod 2)  G_{m}(x)  H_{m}(x)
1  0  palindromic of order 2e  palindromic of order 2e
−1  0  palindromic of order 2e antipalindromic of order 2e
−1  1  antipalindromic of order 2e palindromic of order 2e

Table 2: Palindromic-antipalindromic properties of G_{m}(x), H_{m}(x). We note that G_{m}(−x) = G_{m}(x) and H_{m}(−x) = −H_{m}(x); thus, by Properties iii) and iv)

of Section 2, we have G_{m}(x) = P_{m}(x^{2}), \frac{H_{m}(x)}{x} = Q_{m}(x^{2}), where the palindromic/antipalindromic properties of P_{m}(x), Q_{m}(x) are presented in Table 3.

σ e (mod 2)  P_{m}(x)  Q_{m}(x)
1  0  palindromic of order e  palindromic of order e − 1
−1  0  palindromic of order e antipalindromic of order e − 1
−1  1  antipalindromic of order e palindromic of order e − 1

Table 3: Palindromic-antipalindromic properties of P_{m}(x), Q_{m}(x).

Notice that if σ = −1 (m ≡ −1 (mod 4)), then by Properties i) and ii) both P_{m}(−x) and Q_{m}(−x) are palindromic of order e, e − 1, respectively. We now have

L_{m}^{(ϵ)}(x) = P_{m}(x^{2}) − ϵx\sqrt{m^{∗}}Q_{m}(x^{2}),  (8)

an identity proved in greater generality by Schinzel [10]. If we put C_{m}(x) = P_{m}(x), D_{m}(x) = Q_{m}(x) when σ = 1 and C_{m}(x) = P_{m}(−x), D_{m}(x) = Q_{m}(−x) when σ = −1. We see that both C_{m}(x) and D_{m}(x) are palindromic of order e and e − 1, respectively. We write

C_{m}(x) = ∑_{j=0}^{e} c_{j}x^{e−j} (c_{j} ∈ ℤ, j = 0, 1, …, e)

and

D_{m}(x) = ∑_{j=0}^{e−1} d_{j}x^{e−1−j} (d_{j} ∈ ℤ, j = 0, 1, …, e − 1).

For small values of m, a table of coefficients c_{j} and d_{j} can be found in Riesel [9, Table 34]. Also, Brent [1], has given an efficient algorithm for computing these coefficients.

Note also that

A_{m}^{(ϵ)}(x)A_{m}^{(−ϵ)}(x) = Φ_{m}(x).

Since

A_{m}^{(ϵ)}(−x)A_{m}^{(−ϵ)}(−x) = Φ_{m}(−x),

we get

L_{m}^{(ϵ)}(x)L_{m}^{(−ϵ)}(x) = Φ_{m}(x)Φ_{m}(−x) = Φ_{m}(x^{2}).  (9)

Suppose σ = −1. In this case we must have m^{∗} = −m. If we replace x by ix, where i^{2} = −1, in (8), we get

L_{m}^{(ϵ)}(ix) = P_{m}(−x^{2}) − ϵix\sqrt{m^{∗}}Q_{m}(−x^{2})
= P_{m}(−x^{2}) − ϵx\sqrt{m}Q_{m}(−x^{2})
= C_{m}(x^{2}) − ϵx\sqrt{m}D_{m}(x^{2})  (10)

and

L_{m}^{(ϵ)}(ix)L_{m}^{(−ϵ)}(ix) = Φ_{m}(−x^{2}) = Φ_{2m}(x^{2}).  (11)

Thus, if σ = 1, we have m^{∗} = m and

L_{m}^{(ϵ)}(x) = C_{m}(x^{2}) − ϵx\sqrt{m}D_{m}(x^{2})

and if σ = −1, we have m^{∗} = −m and

L_{m}^{(ϵ)}(ix) = C_{m}(x^{2}) − ϵx\sqrt{m}D_{m}(x^{2}).

4 Aurifeuillian factorizations

For a fixed m, put

F_{n}^{(ϵ)} = β^{ne}L_{m}^{(ϵ)}((−α^{n}/β^{n})^{1/2}).

Notice by (9) and (3)

F_{n}^{(ϵ)}F_{n}^{(−ϵ)} = β^{2ne}Φ_{m}(−α^{n}/β^{n})

= β^{nϕ(m)}Φ_{m}(−α^{n}/β^{n})

= ∏_{d|m} V_{nd}^{μ(m/d)}.

This is the Aurifeuillian factorization of the integer ∏_{d|m} V_{nd}^{μ(m/d)}.

Let R(x), S(x) ∈ ℤ[x], where R(x), S(x) are palindromic of order d, d − 1 respectively. If 2 | d, we can write

R(x) = ∑_{j=0}^{d} r_{j}x^{j} = ∑_{j=0}^{d/2−1} r_{j}(x^{j} + x^{d−j}) + r_{d/2}x^{d/2}  (12)

and

S(x) = ∑_{j=0}^{d−1} s_{j}x^{j} = ∑_{j=0}^{d/2−1} s_{j}(x^{j} + x^{d−1−j}),  (13)

where r_{j} ∈ ℤ(j = 0, 1, …, d/2 − 1) and s_{j} ∈ ℤ(j = 0, 1, …, d/2 − 1). When 2 ∤ d, we can write

R(x) = ∑_{j=0}^{(d−1)/2} r_{j}(x^{j} + x^{d−j}),  (14)

S(x) = ∑_{j=0}^{(d−1)/2} s_{j}(x^{j} + x^{d−1−j}) + s_{(d−1)/2}x^{(d−1)/2},  (15)

(16)

where r_{j} ∈ ℤ (j = 0, 1, …, (d − 1)/2) and s_{j} ∈ ℤ (j = 0, 1, …, (d − 1)/2). We can now establish the following simple theorem.

Theorem 3. Suppose 2 | d, σ = 1 and

K^{(ϵ)}(x) = R(x^{2}) − ϵx\sqrt{m}S(x^{2}),

then

β^{dn}K^{(ϵ)}((−α^{n}/β^{n})^{1/2}) = I_{d,n} + ϵ\sqrt{m}\sqrt{−Q^{n}}(α − β)J_{d,n},

where

I_{d,n} = ∑_{j=0}^{d/2−1} r_{j}(−1)^{j}Q^{nj}V_{(d−2j)n} + (−1)^{d/2}r_{d/2}Q^{nd/2},
J_{d,n} = ∑_{j=0}^{d/2−1} s_{j}(−1)^{j}Q^{nj}U_{(d−2j−1)n}.

Proof. This follows easily from (12) and (13) by putting x = (−α^{n}/β^{n})^{1/2} and noting that

α^{jn}β^{(d−j)n} + α^{(d−j)n}β^{jn} = α^{jn}β^{jn}(α^{(d−2j)n} + β^{(d−2j)n}) = Q^{jn}V_{(d−2j)n}

and

α^{jn}β^{(d−1−j)n} − α^{(d−1−j)n}β^{jn} = α^{jn}β^{jn}(β^{(d−2j−1)n} − α^{(d−2j−1)n}) = −Q^{jn}(α − β)U_{(d−2j−1)n}. Hence,

I_{d,n} = β^{dn}R(−α^{n}/β^{n}), J_{d,n} = β^{(d−1)n}S(−α^{n}/β^{n}).

We also have. Theorem 4. Suppose 2 | d, σ = −1 and

K^{(ϵ)}(ix) = R(x^{2}) − ϵx\sqrt{m}S(x^{2}),

then

β^{dn}K^{(ϵ)}((−α^{n}/β^{n})^{1/2}) = I_{d,n} − ϵ\sqrt{m}\sqrt{Q^{n}}J_{d,n},

where

I_{d,n} = ∑_{j=0}^{d/2−1} r_{j}Q^{nj}V_{(d−2j)n} + r_{d/2}Q^{nd/2},
J_{d,n} = ∑_{j=0}^{d/2−1} s_{j}Q^{nj}V_{(d−2j−1)n}.

Proof. This follows on putting x = (α^{n}/β^{n})^{1/2} and making use of (12) and (13). Theorem 5. Suppose 2 ∤ d and

K^{(ϵ)}(ix) = R(x^{2}) − ϵx\sqrt{m}S(x^{2}),

then

β^{dn}K^{(ϵ)}((−α^{n}/β^{n})^{1/2}) = I_{d,n} − ϵ\sqrt{m}\sqrt{Q^{n}}J_{d,n},

where

I_{d,n} = ∑_{j=0}^{(d−1)/2} r_{j}Q^{nj}V_{(d−2j)n},
J_{d,n} = ∑_{j=0}^{(d−1)/2} s_{j}Q^{nj}V_{(d−2j−1)n} + s_{(d−1)/2}Q^{n(d−1)/2}.

Proof. Putting x = (α^{n}/β^{n})^{1/2} we get

I_{d,n} = β^{dn}R(α^{n}/β^{n}), J_{d,n} = β^{(d−1)n}S(α^{n}/β^{n})

from (14) and (15).

It follows from Theorem 3 that if σ = 1, then

F_{n}^{(ϵ)} = I_{e,n} + ϵ\sqrt{m}\sqrt{−Q^{n}}(α − β)J_{e,n};

if σ = −1, then by Theorems 4 (2 | e) and 5 (2 ∤ e)

F_{n}^{(ϵ)} = I_{e,n} + ϵ\sqrt{m}\sqrt{Q^{n}}J_{e,n}.

In the former case, we see that F_{n}^{(ϵ)} ∈ ℤ if and only if \sqrt{m}\sqrt{−Q^{n}}(α − β) ∈ ℤ; in the latter case we have F_{n}^{(ϵ)} ∈ ℤ if and only if \sqrt{m}\sqrt{Q^{n}} ∈ ℤ. Remark 6. If 2 | e, by Theorem 3 we have for x = (−α^{n}/β^{n})^{1/2}

F_{n}^{(ϵ)} = I_{n} + ϵ\sqrt{m^{∗}}\sqrt{−Q^{n}}(α − β)J_{n},

where in this case

I_{n} = ∑_{j=0}^{e/2−1} c_{j}(−1)^{j}Q^{nj}V_{(e−2j)n} + (−1)^{e/2}c_{e/2}Q^{ne/2},
J_{n} = ∑_{j=0}^{e/2−1} d_{j}(−1)^{j}Q^{nj}U_{(e−2j−1)n}.

If 2 ∤ e, by Theorem 5, we get for x = (α^{n}/β^{n})^{1/2},

F_{n}^{(ϵ)} = I_{n} + ϵ\sqrt{m}\sqrt{Q^{n}}J_{n},

where

I_{n} = ∑_{j=0}^{(e−1)/2} c_{j}Q^{nj}V_{(e−2j)n},
J_{n} = ∑_{j=0}^{(e−3)/2} d_{j}Q^{nj}V_{(e−2j−1)n} + d_{(e−1)/2}Q^{n(e−1)/2}.

We conclude this section with two simple examples.

Example 1: m = 5.

Suppose m = 5; in this case we have e = ϕ(5)/2 = 2 and from [9] we find that c_{0} = 1 and c_{1} = 3 and d_{0} = 1. Thus, by (7) and Theorem 3, we have

F_{n}^{(ϵ)} = I_{e,n} + ϵ\sqrt{5}\sqrt{−Q^{n}}(α − β)J_{e,n},

where

I_{e,n} = c_{0}V_{2n} − c_{1}Q^{n} = V_{2n} − 3Q^{n} = V_{n}^{2} − 5Q^{n},
J_{e,n} = d_{0}U_{n} = U_{n}.

Thus,

V_{5n}/V_{n} = (V_{n}^{2} − 5Q^{n} + \sqrt{5}\sqrt{−Q^{n}}(α − β)U_{n})(V_{n}^{2} − 5Q^{n} − \sqrt{5}\sqrt{−Q^{n}}(α − β)U_{n})

when n is odd we need (α − β) ∈ ℤ in order that F_{n}^{(ϵ)} ∈ ℤ. This will be the case when Q = −1 and P = 1, and we get

V_{5n}/V_{n} = L_{5n}/L_{n} = (L_{n}^{2} + 5 + 5F_{n})(L_{n}^{2} + 5 − 5F_{n}),

which is Jarden’s identity.

Example 2: m = 7.

Suppose m = 7. We get e = ϕ(7)/2 = 3 and c_{0} = 1, c_{1} = 3, d_{0} = 1, d_{1} = 1. By Theorem 5, we get

F_{n}^{(ϵ)} = I_{e,n} + ϵ\sqrt{7}\sqrt{Q^{n}}J_{e,n},

where

I_{e,n} = c_{0}V_{3n} + c_{1}Q^{n}V_{n} = V_{3n} + 3Q^{n}V_{n} = V_{n}^{3},
J_{e,n} = d_{0}V_{2n} + d_{1}Q^{n} = V_{2n} + Q^{n} = V_{n}^{2} − Q^{n}.

Thus,

F_{n}^{(ϵ)} = V_{n}^{3} + ϵ\sqrt{7Q^{n}}(V_{n}^{2} − Q^{n})

and

V_{7n}/V_{n} = F_{n}^{(ϵ)}F_{n}^{(−ϵ)}.

We see that F_{n}^{(ϵ)} ∈ ℤ when n is odd and Q = 7L^{2}. In this case

F_{n}^{(ϵ)} = V_{n}^{3} + ϵ7^{\frac{n+1}{2}} L^{n}(V_{n}^{2} − Q^{n}),

and

V_{7n}/V_{n} = (V_{n}^{3} + 7^{\frac{n+1}{2}} L^{n}(V_{n}^{2} − Q^{n}))(V_{n}^{3} − 7^{\frac{n+1}{2}} L^{n}(V_{n}^{2} − Q^{n})).

5 The main result

Let k be an odd integer such that gcd(k, m) = 1 and we let η denote the Jacobi symbol (k|m). Consider

A_{m}^{(ϵ)}(x^{k}) = ∏_{s∈S_{m}^{(ϵ)}}(x^{k} − ζ_{m}^{s}).

We then have

A_{m}^{(ϵη)}(x^{k}) = ∏_{s∈S_{m}^{(ϵ)}}(x^{k} − ζ_{m}^{sk}).

This is because

{ζ_{m}^{s} : s ∈ S_{m}^{(ϵη)}} = {ζ_{m}^{ks} : s ∈ S_{m}^{(ϵ)}},

which follows from

S_{m}^{(ϵη)} = {s′ : (s′|m) = ϵη, s′ ∈ S_{m}}
= {s′ : s′ ≡ ks (mod m), s ∈ S_{m}^{(ϵ)}}
≡ kS_{m}^{(ϵ)} (mod m).

Put

T_{m,k}^{(ϵ)}(x) = \frac{A_{m}^{(ϵη)}(x^{k})}{A_{m}^{(ϵ)}(x)}

= ∏_{s∈S_{m}^{(ϵ)}} \frac{x^{k} − ζ_{m}^{sk}}{x − ζ_{m}^{s}}

= ∏_{s∈S_{m}^{(ϵ)}} ζ_{m}^{(k−1)s} \frac{(x/ζ_{m}^{s})^{k} − 1}{(x/ζ_{m}^{s}) − 1}.

Let C_{k}(x) denote the polynomial \frac{x^{k}−1}{x−1} ∈ ℤ[x], which is of degree k − 1 and symmetric over ℤ. From

\frac{x^{k} − 1}{x − 1} = ∏_{j=1}^{k−1}(x − ζ_{k}^{j}),

we find that

T_{m,k}^{(ϵ)}(x) = ∏_{s∈S_{m}^{(ϵ)}} ζ_{m}^{(k−1)s} ∏_{j=1}^{k−1}(x/ζ_{m}^{s} − ζ_{k}^{j})

= ∏_{s∈S_{m}^{(ϵ)}} ∏_{j=1}^{k−1}(x − ζ_{m}^{s}ζ_{k}^{j}).

By standard arguments in algebraic number theory, we know that

ζ_{m}^{s}ζ_{k}^{j} where s ∈ S_{m}^{(ϵ)}, j = 1, 2, …, k − 1

are the (k−1)e eigenvalues of a square matrix M of size (k−1)e with entries from O. Indeed, M = C_{1} ⊗ C_{2}, where C_{1} is the companion matrix of C_{k}(x), C_{2} is the companion matrix of A_{m}^{(ϵ)}(x) and ⊗ denotes the Kronecker product. Thus, T_{m,k}^{(ϵ)}(x) is a monic polynomial of degree (k − 1)e in O[x]. It follows that

T_{m,k}^{(ϵ)}(x) = \frac{1}{2}[X_{m,k}(x) − ϵ\sqrt{m^{∗}}W_{m,k}(x)],

where X_{m,k}(x), W_{m,k}(x) ∈ ℤ[x] and X_{m,k}(x) ≡ W_{m,k}(x) (mod 2). From the definition of T_{m,k}^{(ϵ)}(x), it is easy to show that

T_{m,k}^{(ϵ)}(x) = \begin{cases}x^{(k−1)e}T_{m,k}^{(ϵ)}(1/x), & if m ≡ 1 (mod 4); \\ x^{(k−1)e}T_{m,k}^{(−ϵ)}(1/x), & if m ≡ −1 (mod 4). \end{cases}

Thus, when m ≡ 1 (mod 4), both X_{m,k}(x) and W_{m,k}(x) are palindromic of order (k − 1)e and when m ≡ −1 (mod 4), X_{m,k}(x) is palindromic and W_{m,k}(x) is antipalindromic of order (k − 1)e.

By using the arguments in Section 4, we find from (7) that if we define

K_{m,k}^{(ϵ)}(x) = L_{m}^{(ϵη)}(x^{k})/L_{m}^{(ϵ)}(x),

then

K_{m,k}^{(ϵ)}(x) = T_{m,k}^{(ϵ)}(x)T_{m,k}^{(−ϵ)}(−x) = R_{m,k}(x^{2}) − ϵx\sqrt{m^{∗}}S_{m,k}(x^{2}),  (17)

where R_{m,k}(x), S_{m,k}(x) ∈ ℤ[x] with palindromic-antipalindromic properties given in Table 4.

σ  R_{m,k}(x)  S_{m,k}(x)
1 palindromic of order d(k − 1) palindromic of order d(k − 1) − 1
−1 palindromic of order d(k − 1) antipalindromic of order d(k − 1) − 1

Table 4: Palindromic-antipalindromic properties of R_{m,k}(x), S_{m,k}(x).

We are now able to prove a more general version of Jarden’s theorem.

Theorem 7. If σ = 1, n is odd and \sqrt{m}\sqrt{−Q}(α − β) ∈ ℤ, then F_{n}^{(ϵ)}, F_{nk}^{(ϵη)} ∈ ℤ and F_{n}^{(ϵ)} | F_{nk}^{(ϵη)} when k is odd and η = (k|m).

Proof. By (17) and Theorem 3, we see that β^{dn}K_{m,k}^{(ϵ)}(x) ∈ ℤ when k is odd, x = (−α^{n}/β^{n})^{1/2} and d = (k − 1)e. Since

F_{n}^{(ϵ)} = β^{ne}L_{m}((−α^{n}/β^{n})^{1/2}) and F_{nk}^{(ϵη)} = β^{nke}L_{m}((−α^{nk}/β^{nk})^{1/2}),

we see that if σ = 1 and \sqrt{m}\sqrt{−Q}(α − β) ∈ ℤ, then F_{n}^{(ϵ)}, F_{nk}^{(ϵη)} ∈ ℤ. Also, by (17) we see that F_{nk}^{(ϵη)}/F_{n}^{(ϵ)} ∈ ℤ.

If we have integers L, M, S such that

M^{2} + 4(−1)^{\frac{m−1}{2}} L^{2} = mS^{2}  (18)

and put P = M, Q = (−1)^{\frac{m+1}{2}} L^{2}, we get

D = (α − β)^{2} = mS^{2} ⇒ (α − β) = \sqrt{m}S ⇒ \sqrt{m^{∗}}\sqrt{−Q}(α − β) = \sqrt{m}L\sqrt{m}S = mLS ∈ ℤ.

When σ = −1, we define κ = (−1)^{(k−1)/2}. We have

ix^{k} = \begin{cases}(ix)^{k}, & when κ = 1; \\ −(ix)^{k}, & when κ = −1. \end{cases}

It follows from (6) that when κ = 1, we have

A_{m}^{(ϵ)}(ix^{k}) = ∏_{s∈S_{m}^{(ϵ)}}((ix)^{k} − ζ_{m}^{s})

and

A_{m}^{(ϵη)}(ix^{k}) = ∏_{s∈S_{m}^{(ϵ)}}((ix)^{k} − ζ_{m}^{ks}).

As done earlier in this section we find that

A_{m}^{(ϵη)}(ix^{k})/A_{m}^{(ϵ)}(ix) = ∏_{s∈S_{m}^{(ϵ)}} \frac{(ix)^{k} − ζ_{m}^{ks}}{ix − ζ_{m}^{s}} = T_{m,k}^{(ϵ)}(ix).

We are now able to deduce from (7) that

K_{m,k}^{(ϵ)}(ix) = L_{m}^{(ϵη)}(ix^{k})/L_{m}^{(ϵ)}(ix) = T_{m,k}^{(ϵ)}(ix)T_{m,k}^{(−ϵ)}(−ix).  (19)

When κ = −1, we get

A_{m}^{(ϵ)}(ix^{k}) = ∏_{s∈S_{m}^{(ϵ)}}(−(ix)^{k} − ζ_{m}^{s})

and

A_{m}^{(ϵη)}(ix^{k}) = ∏_{s∈S_{m}^{(ϵ)}}(−(ix)^{k} − ζ_{m}^{ks}).

Thus, since k is odd, we have

A_{m}^{(ϵη)}(−ix^{k}) = ∏_{s∈S_{m}^{(ϵ)}}((ix)^{k} − ζ_{m}^{ks}).

Also, since

A_{m}^{(−ϵ)}(ix^{k}) = ∏_{s∈S_{m}^{(−ϵ)}}(−(ix)^{k} − ζ_{m}^{s}) = ∏_{s∈S_{m}^{(−ϵ)}}((−ix)^{k} − ζ_{m}^{s}),

we get

A_{m}^{(−ϵη)}(ix^{k}) = ∏_{s∈S_{m}^{(−ϵ)}}((−ix)^{k} − ζ_{m}^{ks}).

Now from (7), we have

L_{m}^{(−ϵη)}(ix^{k}) = A_{m}^{(−ϵη)}(ix^{k})A_{m}^{(ϵη)}(−ix^{k})

= ∏_{s∈S_{m}^{(−ϵ)}}((−ix)^{k} − ζ_{m}^{ks}) ∏_{s∈S_{m}^{(ϵ)}}((ix)^{k} − ζ_{m}^{ks});

Thus,

\frac{L_{m}^{(−ϵη)}(ix^{k})}{L_{m}^{(ϵ)}(ix)} = ∏_{s∈S_{m}^{(−ϵ)}} \frac{(−ix)^{k} − ζ_{m}^{ks}}{−ix − ζ_{m}^{s}} ∏_{s∈S_{m}^{(ϵ)}} \frac{(ix)^{k} − ζ_{m}^{ks}}{ix − ζ_{m}^{s}} = T_{m,k}^{(−ϵ)}(−ix)T_{m,k}^{(ϵ)}(ix).

By combining this formula with (19) and (17), we get

\frac{L_{m}^{(κηϵ)}(ix^{k})}{L_{m}^{(ϵ)}(ix)} = T_{m,k}^{(ϵ)}(ix)T_{m,k}^{(−ϵ)}(−ix) = K_{m,k}^{(ϵ)}(ix).  (20)

We are now able to prove a version of Theorem 7 when σ = −1.

Theorem 8. If σ = −1, n is odd and \sqrt{mQ} ∈ ℤ, then F_{n}^{(ϵ)}, F_{nk}^{(κηϵ)} ∈ ℤ and F_{n}^{(ϵ)} | F_{nk}^{(κηϵ)} when k is odd and η = (k|m).

Proof. By (17), we have

K_{m,k}^{(ϵ)}(ix) = R_{m,k}(−x^{2}) − ϵi\sqrt{m^{∗}}S_{m,k}(−x^{2}),

where both R_{m,k}(−x), S_{m,k}(−x) are palindromic of order d and d − 1, respectively. Thus, by Theorem 4, we see that

β^{dn}K_{m,k}^{(ϵ)}(ix) ∈ ℤ

when k is odd, x = (−α^{n}/β^{n})^{1/2} and \sqrt{mQ} ∈ ℤ. The remainder of the proof follows in the same way as the proof of Theorem 7.

In the case of σ = −1, we must have \sqrt{mQ} ∈ ℤ, which means that Q = mL^{2}, where L is an integer. Thus, Theorems 7 and 8 are the generalized Jarden crossover theorems for odd, square-free m > 3.

6 Some further remarks

Although we have constrained m > 3, it is possible to prove the crossover theorem in the case that m = 3. Here, we get

F_{n}^{(ϵ)} = V_{n} + ϵ\sqrt{3}Q^{\frac{n}{2}} = V_{n} + ϵ3^{\frac{n+1}{2}} L^{n},

for Q = 3L^{2}. It is a simple matter to verify that

F_{n}^{(ϵ)} | F_{n}^{(−ϵη)}

for odd n, k and

η = (k|m) = \begin{cases}1, & if k ≡ 1 (mod 3); \\ −1, & if k ≡ 2 (mod 3). \end{cases}

Hence, the crossover theorem can also be generalized for m = 3.

We also note that in the case of m ≡ 1 (mod 4), we can write I_{e,n} (and consequently F_{n}^{(ϵ)}) in terms of the (U_{n}) sequence only by making use of the simple identity

V_{2n} = DU_{n}^{2} + 2Q^{n}.

We find that

I_{e,n} = ∑_{j=0}^{e/2−1}(−1)^{j}c_{j}Q^{nj}V_{(e−2j)n} + (−1)^{e/2}c_{e/2}Q^{ne/2}

= D ∑_{j=0}^{e/2−1}(−1)^{j}c_{j}Q^{nj}U_{(e/2−j)n}^{2} + Q^{ne/2} (2 ∑_{j=0}^{e/2−1}(−1)^{j}c_{j} + (−1)^{e/2}c_{e/2}) .

Note that

2 ∑_{j=0}^{e/2−1}(−1)^{j}c_{j} + (−1)^{e/2}c_{e/2} = ∑_{j=0}^{e}(−1)^{j}c_{j} = C_{m}(−1).

Thus,

I_{e,n} = D ∑_{j=0}^{e/2−1}(−1)^{j}c_{j}Q^{nj}U_{(e/2−j)n}^{2} + Q^{ne/2}C_{m}(−1).

By (7) and (8), we have

L_{m}^{(ϵ)}(i) = C_{m}(−1) − ϵi\sqrt{m}D_{m}(−1)

and

L_{m}^{(ϵ)}(i)L_{m}^{(−ϵ)}(i) = Φ_{m}(−1) = 1;

hence,

C_{m}^{2}(−1) + mD_{m}^{2}(−1) = 1,

which, since C_{m}(−1) and D_{m}(−1) ∈ ℤ, means that C_{m}^{2}(−1) = 1 and D_{m}(−1) = 0. By a result in Wagstaff [11, Theorem 2], we have

C_{m}(x^{2}) − \sqrt{m}xD_{m}(x^{2}) = ∏_{s∈S′_{m}}(x^{2} − 2(s|m) cos (\frac{2πs}{m}) x + 1),  (21)

where S′_{m} = \{s : s ∈ S_{m}, s ≤ (m − 1)/2\}. Here we have 2 cos (\frac{2πs}{m}) = ζ_{m}^{s} + ζ_{m}^{−s}. Since m − s ∈ S_{m} whenever s ∈ S_{m}, we see that #S′_{m} = ϕ(m)/2. If we put x = i in (21), we get

C_{m}(−1) = ∏_{s∈S′_{m}} −i(s|m)2 cos (\frac{2πs}{m})

= (−1)^{\frac{ϕ(m)}{4}} ∏_{s∈S′_{m}}(s|m) ∏_{s∈S′_{m}} 2 cos (\frac{2πs}{m}) .

Since (m − s|m) = (−s|m) = (s|m), we see from (5) that

2 ∑_{s∈S′_{m}}(s|m) = ∑_{s∈S_{m}}(s|m) = 0.

Thus, for each s ∈ S′_{m}, there must exist some s^{∗} ∈ S′_{m} (s^{∗} ≠ s) such that (s^{∗}|m) = −(s|m) or (s^{∗}s|m) = −1. It follows that

∏_{s∈S′_{m}}(s|m) = (−1)^{ϕ(m)/4}.

Thus,

C(−1) = ∏_{s∈S′_{m}} 2 cos (\frac{2πs}{m}) .

When m is prime, we know by an old result of Gauss (see [4, (4)]) that

∏_{s∈S′_{m}} 2 cos (\frac{2πs}{m}) = ∏_{s∈S′_{m}} ζ_{m}^{s} + ζ_{m}^{−s} = (−1)^{(m−1)/4}.

If m is composite, there is a very simple proof in Gurak [4, pp. 255–256] that

∏_{s∈S′_{m}} 2 cos (\frac{2πs}{m}) = 1.

It follows that

C(−1) = \begin{cases}(−1)^{(m−1)/4}, & if m is prime; \\ 1, & if m is composite. \end{cases}

References

[1] Richard P. Brent, On computing factors of cyclotomic polynomials, Math. Comput. 61 (1993), 131–149.

[2] John Brillhart, Peter L. Montgomery and Robert D. Silverman, Tables of Fibonacci and Lucas factorizations, Math. Comput. 50 (1988), 251–260.

[3] P. G. Lejeune Dirichlet, Vorlesungen über Zahlentheorie, 4^{th} edition, Supplement VII, Chelsea, 1968.

[4] S. Gurak, Minimal polynomials for Gauss periods with f = 2, Acta Arith. 121 (2007), 233–257.

[5] E. Lucas, Théorèmes d’arithmétique, Atti della Reale Accademia delle scienze di Torino 13 (1878), 271–278.

[6] E. Lucas, Sur les formules de Cauchy et de Lejeune-Dirichlet, Assoc. Française pour l’Avancement des Sciences, Comptes Rendus 7 (1878), 164–173.

[7] Andrew Granville and Peter Pleasants, Aurifeuillian factorization, Math. Comput. 75 (2005), 489–508.

[8] Dov Jarden, Recurring Sequences, 2^{nd} edition, Riveon Lematematika, 1966.

[9] Hans Riesel, Prime Numbers and Computer Methods for Factorization, Birkhaüser, 1985.

[10] A. Schinzel, On primitive prime factors of a^{n} − b^{n}, Math. Proc. Cambridge Philos. Soc. 58 (1962), 555–562.

[11] S. S. Wagstaff, Jr., Aurifeuillian factorizations and the period of the Bell numbers modulo a prime, Math. Comput. 65 (1996), 383–391.

[12] S. S. Wagstaff, Jr., The Joy of Factoring, Volume 68, Student Mathematical Library, American Mathematical Society, 2013.

[13] H. C. Williams, Édouard Lucas and Primality Testing, CMS series of Monographs and Advanced Texts, Volume 22, Wiley-Interscience, John Wiley & Sons, 1998.

2010 Mathematics Subject Classification: Primary 11B37; Secondary 11Y11, 11B50. Keywords: linear recurrence, Lucas function.

Received May 30 2022; revised version received August 8 2022. Published in Journal of Integer Sequences, August 8 2022.

Return to Journal of Integer Sequences home page.