Some Divisibility Properties Concerning Lucas and Elliptic Divisibility Sequences

Chatchawan Panraksa and Aram Tangboonduangjit Mahidol University International College Mahidol University Salaya, Nakhon Pathom 73170 Thailand

                  chatchawan.pan@mahidol.edu
                     aram.tan@mahidol.edu

Abstract We consider sequences of integers formed by a quotient of the Lucas sequences or elliptic divisibility sequences. We then investigate some divisibility properties of these quotient sequences. Additionally, we prove that elliptic divisibility sequences possess a divisibility property that is analogous to a generalization of Matijasevich’s lemma involving the Fibonacci numbers, which contributed to the solution to Hilbert’s tenth problem.

1 Introduction

Let P and Q be relatively prime integers. The Lucas sequence (U_{n}(P, Q))_{n≥0} is defined by U_{0}(P, Q) = 0, U_{1}(P, Q) = 1, and

U_{n}(P, Q) = P · U_{n−1}(P, Q) − Q · U_{n−2}(P, Q) for n ≥ 2.

For example, the Fibonacci sequence (F_{n})_{n≥0} corresponds to U_{n}(1, −1) and the sequence (M_{n})_{n≥0} of Mersenne numbers, where M_{n} = 2^{n} − 1, corresponds to U_{n}(3, 2). Each Lucas sequence (U_{n}(P, Q))_{n≥0} is associated with a characteristic polynomial of the form x^{2} − P x + Q. In this work, if not stated otherwise, (U_{n})_{n≥0} denotes a sequence (U_{n}(P, Q))_{n≥0} for some relatively prime integers P and Q. We also assume that the sequence (U_{n})_{n≥0} is nondegenerate in the sense that Q ≠ 0 and the ratio of the two roots of the associated characteristic polynomial is not a root of unity. Therefore, the discriminant D = P^{2} − 4Q satisfies D ≠ 0, and the two roots α, β of the characteristic polynomial are distinct so that we can express U_{n} explicitly as

U_{n} = \frac{α^{n} − β^{n}}{α − β} = \frac{α^{n} − β^{n}}{\sqrt{D}} .

Another sequence of integers that we consider in this work is called the elliptic divisibility sequence (EDS). It is defined as a sequence of integers (h_{n})_{n≥0} satisfying the recurrence

h_{m+n}h_{m−n} = h_{m+1}h_{m−1}h_{n}^{2} − h_{n+1}h_{n−1}h_{m}^{2}  (1)

for all integers m ≥ n ≥ 0 and being a divisibility sequence; that is, h_{m} | h_{n} whenever m | n. Examples [14] include the sequence of nonnegative integers (n)_{n≥0} and the sequence ((−1)^{(n−1)(n−2)/2}F_{n})_{n≥0}. We can see the latter by realizing the following identity of the Fibonacci numbers:

F_{m+n}F_{m−n} = (−1)^{n+1}(F_{m+1}F_{m−1}F_{n}^{2} − F_{n+1}F_{n−1}F_{m}^{2})  (2)

for all m ≥ n ≥ 0. (We can readily verify the identity (2) by appealing to the well-known Catalan identity F_{n+r}F_{n−r} = F_{n}^{2} + (−1)^{n+r+1}F_{r}^{2} for all integers n and r.) This means EDS gives us a natural way to generalize the Fibonacci sequence. It also gives examples of divisibility sequences that do not satisfy linear recurrences. A sequence (h_{n})_{n≥0} with h_{0} = 0, h_{1} = 1, and h_{2}h_{3} ≠ 0 is said to be proper. Ward [14] was the first to study arithmetic properties of proper elliptic divisibility sequences. One of his results states that a proper sequence (h_{n})_{n≥0} satisfying (1) is an elliptic divisibility sequence if and only if h_{2}, h_{3}, h_{4} are integers and h_{2} | h_{4}.

However, we can give an alternative definition of EDS via elliptic curves. We recall some theories of elliptic curves. In particular, we consider a curve with the Weierstrass equation given by

y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}  (3)

with integer coefficients. Non-singular rational points on the projective closure of this curve form a group E(ℚ); see, for instance, [11]. Let P be a non-identity element in this group. For a positive integer n, we denote the addition of point P to itself P + P + ⋯ + P up to n terms by nP. Then the corresponding coordinate point (x(nP), y(nP)) on the curve can be expressed by

(x(nP), y(nP)) = (\frac{A_{nP}}{B_{nP}^{2}} , \frac{C_{nP}}{B_{nP}^{3}} )

where A_{nP} and C_{nP} are integers, B_{nP} is a positive integer, and the fractions in the coordinates are in reduced forms.

It is now conventional to define an elliptic divisibility sequence as follows.

Definition 1. Let E/ℚ be an elliptic curve with the Weierstrass equation given by (3). Let P ∈ E(ℚ) be a non-torsion point. For each positive integer n, denote the integer B_{nP} by B_{n}. Then the sequence (B_{n})_{n≥1} is said to be an elliptic divisibility sequence (EDS). An EDS (B_{n})_{n≥1} is said to be normalized if B_{1} = 1. We can normalize an EDS by a change of variables in the defining Weierstrass equation. The obtained sequence (B_{n}/B_{1})_{n≥1} is then an EDS.

In this work, we follow Definition 1 for the definition of the elliptic divisibility sequence. If not stated otherwise, all elliptic divisibility sequences are assumed to be normalized. See, for example, [15, 10] for the connection between the two definitions of the elliptic divisibility sequence. Elliptic divisibility sequences have gained popularity recently due to their application in cryptography; see, for example, [13]. In Section 2, we define a new sequence as a ratio of Lucas sequences and study specific arithmetic properties this sequence possesses. In Section 3, we do the same for elliptic divisibility sequences. In 1970, Matijasevich [4] completed the theorem (based on combined work by Davis, Putnam, and Robinson) that solved Hilbert’s tenth problem. Part of the proof of this theorem used specific arithmetic properties of the Fibonacci numbers. Onphaeng and Pongsriiam [5] generalized one of these properties to the Lucas sequences. The final result of this paper (Theorem 16) generalizes the exact property to elliptic divisibility sequences.

2 Lucas sequences

A sequence (u_{n}) of integers is said to be a strong divisibility sequence if gcd(u_{m}, u_{n}) = u_{gcd(m,n)} for all m, n. Let N be a positive integer. A sequence (u_{n}) of rational numbers is said to be an N-almost strong divisibility sequence if for all m and n where u_{m} and u_{n} are integers we have gcd(u_{m}, u_{n}) = u_{gcd(m,n)} whenever gcd(mn, N) = 1. Let the sequence (T_{n})_{n≥1} be defined by

T_{n} =|\frac{U_{nΔ}}{U_{n}U_{Δ}} | ,  (4)

where Δ = |D| and D is the discriminant of the characteristic polynomial associated with the Lucas sequence (U_{n})_{n≥0}. In general, some of the terms of this sequence might not be integers. For example, for the sequence U(4, −7), we have Δ = 12 and the first five terms of the sequence

T_{n} =|\frac{U_{12n}}{U_{12}U_{n}} |

are

1, \frac{76751}{2}, \frac{3240525601}{3}, \frac{158095946378449}{2}, 7471977820027132645

while for the Fibonacci sequence F_{n} = U_{n}(1, −1), we have Δ = 5 and the first five terms of the sequence

T_{n} = \frac{F_{5n}}{5F_{n}}  (5)

are

1, 11, 61, 451, 3001.

We can show that each term of the sequence (5) is an integer [6]. Filipponi and Freitag [1] gave the Zeckendorf decomposition of the sequence (5). The present authors [6] also studied and gave certain curious arithmetic properties of the sequence (5) . In particular, we proved that T_{n}^{k} divides T (nT (nT (⋯ (nT (n))))) exactly, where n appears k times in this composition of indices. For example, for k = 4, we have

T_{n}^{4} ∥ T (nT (nT (nT (n)))),

where a^{n} ∥ b means a^{n} divides b exactly, that is, a^{n} divides b but a^{n+1} does not. In this work, we generalize this result to the sequence (T_{n})_{n≥1} defined in terms of the Lucas sequences in (4) (Corollary 11). We also prove that this sequence (T_{n})_{n≥1} is a Δ-almost strong divisibility sequence (Theorem 7).

2.1 p-adic valuations of Lucas sequences

If p is a prime such that p ∤ Q, then the rank of apparition of p in the sequence (U_{n})_{n≥0}, denoted τ(p), is defined to be the least positive integer such that p | U_{τ(p)}. The following basic facts about τ(p) are well-known: τ(p) exists for each p, and p | U_{n} if and only if τ(p) | n. Sanna [9] gave an explicit formula for the p-adic valuation ν_{p}(U_{n}) of nondegenerate Lucas sequences in terms of the prime p, the index n, and the rank of apparition τ(p), generalizing the result by Lengyel [3] who gave the same formula but only for the Fibonacci sequence. We quote this result by Sanna [9, Thm. 1.5, Cor. 1.6] as Theorem 2 below.

Theorem 2. Let p be a prime such that p ∤ Q. Then, for each positive integer n,

ν_{p}(U_{n}) = \begin{cases}ν_{p}(n) + ν_{p}(U_{p}) − 1, & p | D and p | n; \\ 0, & p | D and p ∤ n; \\ ν_{p}(n) + ν_{p}(U_{pτ(p)}) − 1, & p ∤ D, τ(p) | n, and p | n; \\ ν_{p}(U_{τ(p)}), & p ∤ D, τ(p) | n, and p ∤ n; \\ 0, & p ∤ D and τ(p) ∤ n. \end{cases}

In particular, if p is an odd prime such that p ∤ Q, then, for each positive integer n,

ν_{p}(U_{n}) = \begin{cases}ν_{p}(n) + ν_{p}(U_{p}) − 1, & p | D and p | n; \\ 0, & p | D and p ∤ n; \\ ν_{p}(n) + ν_{p}(U_{τ(p)}), & p ∤ D and τ(p) | n; \\ 0, & p ∤ D and τ(p) ∤ n. \end{cases}

Remark 3. If p is a prime and p | Q then since gcd(P, Q) = 1, we can prove by induction that ν_{p}(U_{n}) = 0 for all n ≥ 1. In fact, since U_{1} = 1, we have p ∤ U_{1}. Assume that p ∤ U_{n−1} for some n ≥ 2. If p | U_{n}, then since P U_{n−1} = U_{n} + QU_{n−2}, p | Q, and p ∤ U_{n−1}, it follows that p | P contradicting the assumption that gcd(P, Q) = 1. Hence p ∤ U_{n}.

We also need the following result by the present authors [7, Lem. 2.3] for p-adic valuation of Lucas sequence with integer-multiple index.

Lemma 4. Let n, k ≥ 1 and p a prime factor of U_{k} such that p ∤ Q. Then

1. if (i) p is odd, or (ii) p = 2 and k is even, or (iii) p = 2 and n is odd, we have

ν_{p}(U_{kn}) = ν_{p}(n) + ν_{p}(U_{k});

2. if k and D are odd and n is even, we have

ν_{2}(U_{kn}) = ν_{2}(n) + ν_{2}(U_{k}) + (ν_{2}(U_{2τ(2)}) − ν_{2}(U_{τ(2)}) − 1) ≥ ν_{2}(n) + ν_{2}(U_{k}).

We now state some properties of the sequence (T_{n})_{n≥1}.

Lemma 5. Suppose gcd(n, Δ) = 1. Then T_{n} is an integer.

Proof. Since gcd(P, Q) = 1, it follows that (U_{n})_{n≥0} is a strong divisibility sequence. From the definition of T_{n}, it suffices to show that gcd(U_{n}, U_{Δ}) = 1. Indeed, we have gcd(U_{n}, U_{Δ}) = U_{gcd(n,Δ)} = U_{1} = 1.

Lemma 6. Suppose gcd(n, Δ) = 1. Then gcd(T_{n}, Δ) = 1 = gcd(T_{n}, U_{n}).

Proof. To prove gcd(T_{n}, Δ) = 1, suppose p is a prime factor of Δ. Then by Theorem 2, since gcd(n, Δ) = 1 and p | Δ, we have

ν_{p}(U_{nΔ}) = ν_{p}(nΔ) + ν_{p}(U_{p}) − 1 = ν_{p}(n) + ν_{p}(Δ) + ν_{p}(U_{p}) − 1
= ν_{p}(Δ) + ν_{p}(U_{p}) − 1

and

ν_{p}(U_{n}U_{Δ}) = ν_{p}(U_{n}) + ν_{p}(U_{Δ}) = 0 + ν_{p}(Δ) + ν_{p}(U_{p}) − 1
= ν_{p}(Δ) + ν_{p}(U_{p}) − 1.

We see that ν_{p}(U_{nΔ}) = ν_{p}(U_{n}U_{Δ}). Therefore, gcd(T_{n}, Δ) = 1.

To prove gcd(T_{n}, U_{n}) = 1, suppose p is a prime divisor of U_{n}. If p | Δ, then since gcd(n, Δ) = 1, we have p ∤ n. By Theorem 2, it follows that ν_{p}(U_{n}) = 0, contradicting the fact that p is a prime divisor of U_{n}. Thus p ∤ Δ. By case (1) of Lemma 4, we have

ν_{p}(U_{nΔ}) = ν_{p}(Δ) + ν_{p}(U_{n}) = 0 + ν_{p}(U_{n}) = ν_{p}(U_{n}).

This implies ν_{p}(T_{n}) = 0 and therefore gcd(T_{n}, U_{n}) = 1.

2.2 Almost strong divisibility property

Theorem 7. The sequence (T_{n})_{n≥1} is a Δ-almost strong divisibility sequence.

Proof. Suppose m and n satisfy gcd(mn, Δ) = 1. Let p be a prime such that p | T_{m} and p | T_{n}. By Lemma 6, p ∤ U_{m}, p ∤ U_{n}, and p ∤ Δ. If p is odd, by Theorem 2 we have

ν_{p}(T_{m}) = ν_{p}(U_{mΔ}) − ν_{p}(U_{Δ}) = ν_{p}(mΔ) + ν_{p}(U_{τ(p)}) − ν_{p}(U_{Δ})
= ν_{p}(m) + ν_{p}(U_{τ(p)}) − ν_{p}(U_{Δ}).

Similarly, we have ν_{p}(T_{n}) = ν_{p}(n) + ν_{p}(U_{τ(p)}) − ν_{p}(U_{Δ}). Let ℓ = gcd(m, n). Then

ν_{p}(T_{ℓ}) = ν_{p}(U_{ℓΔ}) − ν_{p}(U_{Δ}) = ν_{p}(ℓ) + ν_{p}(U_{τ(p)}) − ν_{p}(U_{Δ})
= min{ν_{p}(m), ν_{p}(n)} + ν_{p}(U_{τ(p)}) − ν_{p}(U_{Δ}).

For p = 2, we consider four cases. Case 1: Suppose p | m and p | n. We have

ν_{p}(T_{m}) = ν_{p}(U_{mΔ}) − ν_{p}(U_{Δ}) = ν_{p}(mΔ) + ν_{p}(U_{pτ(p)}) − 1 − ν_{p}(U_{Δ})
= ν_{p}(m) + ν_{p}(U_{pτ(p)}) − 1 − ν_{p}(U_{Δ}).

Similarly, we have ν_{p}(T_{n}) = ν_{p}(n) + ν_{p}(U_{pτ(p)}) − 1 − ν_{p}(U_{Δ}). Let ℓ = gcd(m, n) so that p | ℓ. Then

ν_{p}(T_{ℓ}) = ν_{p}(U_{ℓΔ}) − ν_{p}(U_{Δ}) = ν_{p}(ℓ) + ν_{p}(U_{pτ(p)}) − 1 − ν_{p}(U_{Δ})
= min{ν_{p}(m), ν_{p}(n)} + ν_{p}(U_{pτ(p)}) − 1 − ν_{p}(U_{Δ}).

Case 2: Suppose p ∤ m and p | n. We have

ν_{p}(T_{m}) = ν_{p}(U_{mΔ}) − ν_{p}(U_{Δ}) = ν_{p}(U_{τ(p)}) − ν_{p}(U_{Δ})

and

ν_{p}(T_{n}) = ν_{p}(n) + ν_{p}(U_{pτ(p)}) − 1 − ν_{p}(U_{Δ}) ≥ ν_{p}(U_{pτ(p)}) − ν_{p}(U_{Δ})
≥ ν_{p}(U_{τ(p)}) − ν_{p}(U_{Δ}).

Let ℓ = gcd(m, n) so that p ∤ ℓ. Then

ν_{p}(T_{ℓ}) = ν_{p}(U_{ℓΔ}) − ν_{p}(U_{Δ}) = ν_{p}(U_{τ(p)}) − ν_{p}(U_{Δ}) = min{ν_{p}(T_{m}), ν_{p}(T_{n})}.

Case 3: Suppose p | m and p ∤ n. This is analogous to Case 2. Case 4: Suppose p ∤ m and p ∤ n. This is also analogous to Case 2.

We have shown that ν_{p}(gcd(T_{m}, T_{n})) = ν_{p}(T_{gcd(m,n)}) for all primes p. Hence

gcd(T_{m}, T_{n}) = T_{gcd(m,n)},

as we wish to show.

2.3 Nested exact divisibility property

Let n be a positive integer. Define the sequence (H_{k}(n))_{k≥1} by H_{1}(n) = T_{n} and H_{k}(n) = T_{nH_{k−1}(n)} for k ≥ 2. The first few terms of the sequence (H_{k}(n))_{k≥1} are

T (n), T (nT (n)), T (nT (nT (n))), T (nT (nT (nT (n)))).

We see that this forms a subsequence of (T_{m})_{m≥1} for each n, and the sequence of nested indices is increasing very rapidly. We first observe the following property of the sequence (H_{k}(n))_{k≥1}.

Lemma 8. Suppose gcd(n, Δ) = 1. Then gcd(U_{nH_{k}(n)}, T_{n}) = 1 for all positive integers k.

Proof. We prove that gcd(H_{k}(n), Δ) = 1 for all positive integers k by induction. For k = 1, by Lemma 6, we have

gcd(H_{k}(n), Δ) = gcd(H_{1}(n), Δ) = gcd(T_{n}, Δ) = 1.

Assume that gcd(H_{k}(n), Δ) = 1 for some k ≥ 1. Then gcd(nH_{k}(n), Δ) = 1 and by Lemma 6, we have

gcd(H_{k+1}(n), Δ) = gcd(T_{nH_{k}(n)}, Δ) = 1.

Now since (U_{n})_{n≥0} is a strong divisibility sequence, we have

gcd(U_{nH_{k}(n)}, U_{nΔ}) = U_{gcd(nH_{k}(n),nΔ)} = U_{n·gcd(H_{k}(n),Δ)} = U_{n}.

Hence

gcd(U_{nH_{k}(n)}, T_{n}) = gcd (U_{nH_{k}(n)}, \frac{U_{nΔ}}{U_{n}U_{Δ}} ) = 1.

Lemma 9. Suppose gcd(n, Δ) = 1. If 2 | T_{n}, then 2 | nΔ.

Proof. We proceed by contradiction. Assume that nΔ is odd. Then both n and Δ are odd. Since 2 | T_{n}, we have 2 | U_{nΔ} so that ν_{2}(U_{nΔ}) ≥ 1. Consequently, Theorem 2 implies that ν_{2}(U_{nΔ}) = ν_{2}(U_{τ(2)}) and τ(2) | nΔ. Since Δ is odd, we have that P is odd and thus, by Remark 3, τ(2) = 3. Therefore ν_{2}(U_{nΔ}) = ν_{2}(U_{3}) and 3 | nΔ. This implies 3 | Δ or 3 | n. If 3 | Δ, by the fact that (U_{n})_{n≥0} is a divisibility sequence, we have

ν_{2}(U_{3}) = ν_{2}(U_{nΔ}) ≥ ν_{2}(U_{Δ}) ≥ ν_{2}(U_{3}).

This yields ν_{2}(U_{Δ}) = ν_{2}(U_{3}). Similarly, if 3 | n, then ν_{2}(U_{n}) = ν_{2}(U_{3}). Consequently, max{ν_{2}(U_{Δ}), ν_{2}(U_{n})} = ν_{2}(U_{3}), and we have

0 ≤ ν_{2}(T_{n}) = ν_{2}(\frac{U_{nΔ}}{U_{n}U_{Δ}} )

≤ min \{ν_{2}(\frac{U_{nΔ}}{U_{n}} ), ν_{2}(\frac{U_{nΔ}}{U_{Δ}} )\}

= ν_{2}(U_{nΔ}) − ν_{2}(U_{3}) = ν_{2}(U_{3}) − ν_{2}(U_{3}) = 0.

Hence, ν_{2}(T_{n}) = 0, contradicting the assumption that 2 | T_{n}.

We have the following theorem about the exact divisibility property of the sequence (H_{k}(n))_{k≥1}.

Theorem 10. Suppose gcd(n, Δ) = 1. Let p be a prime such that ν_{p}(T_{n}) > 0. Then ν_{p}(H_{k}(n)) = kν_{p}(T_{n}) for all positive integers k.

Proof. We prove by induction on k. The case when k = 1 is obvious. Assume that the statement holds for some positive integer k. Let p be a prime such that p | T_{n}. Put a = ν_{p}(T_{n}) ≥ 1. Then

ν_{p}(T_{n}^{k}) = ka = ν_{p}(H_{k}(n)).

Since p | T_{n}, it follows from Lemma 6 that p ∤ U_{n} and from Lemma 8 that p ∤ U_{nH_{k}(n)}. Thus,

ν_{p}(H_{k+1}(n)) = ν_{p}(T_{nH_{k}(n)}) = ν_{p} (\frac{U_{nH_{k}(n)·Δ}}{U_{nH_{k}(n)}U_{Δ}} ) = ν_{p}(U_{nH_{k}(n)·Δ}) − ν_{p}(U_{Δ}).

If p is odd, then, by Theorem 2 and Lemma 4, we have

ν_{p}(U_{nH_{k}(n)·Δ}) − ν_{p}(U_{Δ}) = ν_{p}(H_{k}(n)) + ν_{p}(U_{nΔ}) − ν_{p}(U_{Δ})

= ka + ν_{p} (\frac{U_{nΔ}}{U_{Δ}} ) = ka + ν_{p} (\frac{U_{nΔ}}{U_{n}U_{Δ}} )

= ka + ν_{p}(T_{n}) = ka + a = (k + 1)a.

If p = 2, then by Lemma 9, we have that nΔ is even and by case 1 (ii) of Lemma 4, we have the same result as above. Hence, for all primes p, we have

ν_{p}(H_{k+1}(n)) = (k + 1)a = (k + 1)ν_{p}(T_{n}).

We conclude this section with an immediate corollary.

Corollary 11. Suppose gcd(n, Δ) = 1 and T_{n} ≠ 1. Then, for each positive integer k,

T_{n}^{k} ∥ H_{k}(n).

3 Elliptic divisibility sequences

We have the following result summarized by Reynolds [8, Lem. 2.1] for specific basic arithmetic properties of elliptic divisibility sequences.

Lemma 12. Let (B_{n})_{n≥1} be an elliptic divisibility sequence corresponding to an elliptic curve E with the Weierstrass equation (3) and a non-torsion point P in E(ℚ).

(i) Let p be a prime. There exists a smallest positive integer n_{0} such that p | B_{n_{0}}. Moreover, for every positive integer n,

p | B_{n} if and only if n_{0} | n.

(ii) Let p be an odd prime. For every pair of positive integers m, n, if ν_{p}(B_{n}) > 0 then

ν_{p}(B_{mn}) = ν_{p}(B_{n}) + ν_{p}(m).

(iii) For every pair of positive integers m, n, if ν_{2}(B_{n}) > 0 then

ν_{2}(B_{mn}) = ν_{2}(B_{n}) + ν_{2}(m)

if the coefficient a_{1} is even and

|ν_{2}(B_{mn}) − (ν_{2}(B_{n}) + ν_{2}(m))| ≤ ϵ

otherwise, where the constant ϵ depends only on E and P.

(iv) For all positive integers m, n,

gcd(B_{m}, B_{n}) = B_{gcd(m,n)}.

Now we define a sequence similar in the form to sequence (5) but in the context of elliptic divisibility sequences. Let τ be a positive integer and (B_{n})_{n≥1} an elliptic divisibility sequence corresponding to an elliptic curve with the Weierstrass equation (3) and a non-torsion point P. We define the sequence (K_{n})_{n≥1} as follows. For each positive integer n, let

K_{n} = \frac{B_{τn}}{B_{τ}B_{n}} .

Then we have the following result.

Theorem 13. Let (K_{n})_{n≥1} be a sequence defined as above with the coefficient a_{1} in the Weierstrass equation (3) being even and τ | B_{τ}. Then (K_{n})_{n≥1} is a τ-almost strong divisibility sequence. That is, for all positive integers m, n, if gcd(mn, τ) = 1, then

gcd(K_{m}, K_{n}) = K_{gcd(m,n)}.

Proof. Let m and n be positive integers that are relatively prime to τ. By Lemma 12(iv), we have B_{τ} | B_{τn} and B_{n} | B_{τn}. Since gcd(n, τ) = 1, it follows that K_{n} is an integer. Similarly, we have that K_{m} is an integer. Let p be a prime. We consider two cases.

Case 1: Suppose ν_{p}(B_{τ}) > 0. Since gcd(τ, mn) = 1, by Lemma 12(iv), we have ν_{p}(B_{n}) = 0 = ν_{p}(B_{m}). By Lemma 12(ii, iii), we have ν_{p}(B_{τn}) = ν_{p}(B_{τ}) + ν_{p}(n) and ν_{p}(B_{τm}) = ν_{p}(B_{τ}) + ν_{p}(m). This implies that

ν_{p}(K_{n}) = ν_{p}(B_{τn}) − ν_{p}(B_{τ}) − ν_{p}(B_{n})
= ν_{p}(B_{τ}) + ν_{p}(n) − ν_{p}(B_{τ}) − 0
= ν_{p}(n).

Similarly, we have ν_{p}(K_{m}) = ν_{p}(m). Consequently,

ν_{p}(gcd(K_{m}, K_{n})) = min{ν_{p}(K_{m}), ν_{p}(K_{n})} = min{ν_{p}(m), ν_{p}(n)}.

Now, we consider ν_{p}(K_{gcd(m,n)}). By Lemma 12(iv), we observe that

ν_{p}(B_{gcd(m,n)}) = ν_{p}(gcd(B_{m}, B_{n})) = min{ν_{p}(B_{m}), ν_{p}(B_{n})} = 0.

By Lemma 12(ii, iii), we obtain that

ν_{p}(K_{gcd(m,n)}) = ν_{p}(B_{τ·gcd(m,n)}) − ν_{p}(B_{τ}) − ν_{p}(B_{gcd(m,n)})
= ν_{p}(B_{τ}) + ν_{p}(gcd(m, n)) − ν_{p}(B_{τ}) − ν_{p}(B_{gcd(m,n)})
= ν_{p}(gcd(m, n)) = min{ν_{p}(m), ν_{p}(n)}.

Comparing the values, we conclude that

ν_{p}(gcd(K_{m}, K_{n})) = ν_{p}(K_{gcd(m,n)}).

Case 2: Suppose ν_{p}(B_{τ}) = 0. We consider three subcases. Case 2.1: Suppose ν_{p}(B_{m}) = 0 and ν_{p}(B_{n}) = 0. We have,

ν_{p}(K_{n}) = ν_{p}(B_{τn}) − ν_{p}(B_{τ}) − ν_{p}(B_{n}) = ν_{p}(B_{τn}).

Similarly, we have ν_{p}(K_{m}) = ν_{p}(B_{τm}). Consequently, by Lemma 12(iv),

ν_{p}(gcd(K_{m}, K_{n})) = ν_{p}(gcd(B_{τm}, B_{τn})) = ν_{p}(B_{gcd(τm,τn)}) = ν_{p}(B_{τ·gcd(m,n)}).

On the other hand, since min{ν_{p}(B_{m}), ν_{p}(B_{n})} = 0, we have, by Lemma 12(iv),

ν_{p}(B_{gcd(m,n)}) = ν_{p}(gcd(B_{m}, B_{n})) = min{ν_{p}(B_{m}), ν_{p}(B_{n})} = 0.

Hence,

ν_{p}(K_{gcd(m,n)}) = ν_{p}(B_{τ·gcd(m,n)}) − ν_{p}(B_{τ}) − ν_{p}(B_{gcd(m,n)}) = ν_{p}(B_{τ·gcd(m,n)}).

Comparing the values, we conclude that

ν_{p}(gcd(K_{m}, K_{n})) = ν_{p}(K_{gcd(m,n)}).

Case 2.2: Suppose ν_{p}(B_{m}) > 0 and ν_{p}(B_{n}) > 0. By Lemma 12(ii, iii), we have ν_{p}(B_{τn}) = ν_{p}(B_{n}) + ν_{p}(τ). Therefore,

ν_{p}(K_{n}) = ν_{p}(B_{τn}) − ν_{p}(B_{τ}) − ν_{p}(B_{n})
= ν_{p}(B_{n}) + ν_{p}(τ) − ν_{p}(B_{τ}) − ν_{p}(B_{n})
= ν_{p}(τ).

Similarly, we have ν_{p}(K_{m}) = ν_{p}(τ). Thus,

ν_{p}(gcd(K_{m}, K_{n})) = min{ν_{p}(K_{m}), ν_{p}(K_{n})} = ν_{p}(τ).

On the other hand, since ν_{p}(B_{m}) > 0 and ν_{p}(B_{n}) > 0, by Lemma 12(iv), it follows that ν_{p}(B_{gcd(m,n)}) > 0. By Lemma 12(ii), we have

ν_{p}(K_{gcd(m,n)}) = ν_{p}(B_{τ·gcd(m,n)}) − ν_{p}(B_{τ}) − ν_{p}(B_{gcd(m,n)})
= ν_{p}(B_{gcd(m,n)}) + ν_{p}(τ) − ν_{p}(B_{τ}) − ν_{p}(B_{gcd(m,n)})
= ν_{p}(τ).

Again, for this case, we have

ν_{p}(gcd(K_{m}, K_{n})) = ν_{p}(K_{gcd(m,n)}).

Case 2.3: Suppose ν_{p}(B_{m}) > 0 and ν_{p}(B_{n}) = 0. By following the same argument as in Case 2.1 and Case 2.2, we have ν_{p}(K_{m}) = ν_{p}(τ) and ν_{p}(K_{n}) = ν_{p}(B_{τn}). Since τ | B_{τ}, by Lemma 12(iv), we have

ν_{p}(gcd(K_{m}, K_{n})) = ν_{p}(gcd(τ, B_{τn})) ≤ ν_{p}(gcd(B_{τ}, B_{τn})) = ν_{p}(B_{τ}) = 0.

Hence, ν_{p}(gcd(K_{m}, K_{n})) = 0. Now we claim that ν_{p}(K_{gcd(m,n)}) = 0. Since, by Lemma 12(iv), ν_{p}(B_{gcd(m,n)}) = ν_{p}(gcd(B_{m}, B_{n})) = min{ν_{p}(B_{m}), ν_{p}(B_{n})} = 0, it follows that

ν_{p}(K_{gcd(m,n)}) = ν_{p}(B_{τ·gcd(m,n)}) − ν_{p}(B_{τ}) − ν_{p}(B_{gcd(m,n)}) = ν_{p}(B_{τ·gcd(m,n)}).

Assume that ν_{p}(B_{τ·gcd(m,n)}) > 0. Since ν_{p}(B_{m}) > 0, by Lemma 12(i), there exists a smallest positive integer m_{0} such that ν_{p}(B_{m_{0}}) > 0 and m_{0} | m. Since p | B_{τ·gcd(m,n)}, by Lemma 12(i), m_{0} | τ · gcd(m, n). Since gcd(mn, τ) = 1 and m_{0} | m, we have gcd(m_{0}, τ) = 1. Consequently, m_{0} | gcd(m, n). This implies m_{0} | n, so that, by Lemma 12(i), ν_{p}(B_{n}) > 0, which is a contradiction. Hence, ν_{p}(B_{τ·gcd(m,n)}) = 0 = ν_{p}(K_{gcd(m,n)}). We conclude for this case that

ν_{p}(gcd(K_{m}, K_{n})) = ν_{p}(K_{gcd(m,n)}).

Combining all cases, we have proved that for every prime p, we have

ν_{p}(gcd(K_{m}, K_{n})) = ν_{p}(K_{gcd(m,n)}).

Hence

gcd(K_{m}, K_{n}) = K_{gcd(m,n)},

as desired.

We point out that the condition in Theorem 13 on integer τ dividing B_{τ} is not particularly restrictive. This condition is investigated extensively in [2, 10].

Example 14. [10] The elliptic divisibility sequence (B_{n})_{n≥1} corresponding to elliptic curve E : y^{2} + y = x^{3} − x and non-torsion point P = (0, 0) is

(1, 1, 1, 1, 2, 1, 3, 5, 7, 4, 23, 29, 59, 129, 314, 65, 1529, 3689, 8209, 16264, 83313, …).

(See [12, \underline{A006769}].) The indices τ with the property τ | B_{τ} are

1, 40, 53, 63, 80, 127, 160, 189, 200, 320, 400, 441, 443, ….

According to Theorem 13 with τ = 40, the sequence (K_{n})_{n≥1} defined by

K_{n} = \frac{B_{40n}}{B_{40}B_{n}} = \frac{B_{40n}}{(40 · 13526278251270010)B_{n}}

for all n ≥ 1 satisfies gcd(K_{m}, K_{n}) = K_{gcd(m,n)} whenever gcd(mn, 40) = 1.

The following result is an analog to Theorem 10 for p-adic valuation of sequence with nested indices. Here again, to describe the nth term of a sequence (a_{n}), we use the function notation a(n) interchangeably with the subscript notation a_{n}.

Theorem 15. Let (B_{n})_{n≥1} be an elliptic divisibility sequence corresponding to an elliptic curve whose Weierstrass equation (3) has coefficient a_{1} even. Let n be a positive integer. Define a sequence (G_{k}(n))_{k≥1} as follows: G_{1}(n) = B_{n} and G_{k+1}(n) = B(nG_{k}(n)) for k ≥ 1. Let p be a prime number. If ν_{p}(B_{n}) > 0, then

ν_{p}(G_{k}(n)) = kν_{p}(B_{n}).

Therefore, if B_{n} ≠ 1, then B_{n}^{k} ∥ G_{k}(n) for all positive integers k.

Proof. We prove by induction on k. For k = 1, we have G_{1}(n) = B_{n}. Hence the statement holds. Assume that the statement holds for some positive integer k. Then, Lemma 12(ii, iii), we have

ν_{p}(G_{k+1}(n)) = ν_{p}(B(nG_{k}(n))) = ν_{p}(G_{k}(n)) + ν_{p}(B_{n})
= kν_{p}(B_{n}) + ν_{p}(B_{n}) = (k + 1)ν_{p}(B_{n}).

By mathematical induction, the statement holds for all positive integers k.

The final result is a generalization of Matijasevich’s lemma [4, Lem. 17] for elliptic divisibility sequences. Matijasevich’s lemma states that for n > 2 we have F_{n}^{2} | F_{m} if and only if nF_{n} | m where (F_{n})_{n≥0} is the Fibonacci sequence.

Theorem 16. Let (B_{n})_{n≥1} be an elliptic divisibility sequence corresponding to an elliptic curve whose Weierstrass equation (3) has coefficient a_{1} even. Moreover, suppose that there exists a positive integer N such that all terms of the sequence (B_{n})_{n≥N} are distinct and none of the terms B_{1}, …, B_{N−1} appears in (B_{n})_{n≥N}. Then, for all integers n, r ≥ N and for all positive integers k, we have B_{n}^{k} | B_{r} if and only if nB_{n}^{k−1} | r.

Proof. Let n, r be at least N and k a positive integer. Assume that B_{n}^{k} | B_{r}. Since B_{n} | B_{r}, by Lemma 12(iv), we have B_{gcd(n,r)} = gcd(B_{n}, B_{r}) = B_{n}. Since all terms of the sequence (B_{n})_{n≥N} are distinct and none is equal to any B_{1}, …, B_{N−1}, it follows that gcd(n, r) = n and therefore n | r. Write r = ns for some positive integer s and let p be a prime dividing nB_{n}. We consider two cases. Case 1: Suppose p | B_{n}. Let ν_{p}(B_{n}) = ℓ ≥ 1. Then kℓ = ν_{p}(B_{n}^{k}) ≤ ν_{p}(B_{r}). By Lemma 12(ii, iii), we have

kℓ ≤ ν_{p}(B_{r}) = ν_{p}(B_{ns}) = ν_{p}(B_{n}) + ν_{p}(s) = ℓ + ν_{p}(s).

Thus, ν_{p}(s) ≥ (k − 1)ℓ. Consequently,

ν_{p}(nB_{n}^{k−1}) = ν_{p}(n) + ν_{p}(B_{n}^{k−1}) = ν_{p}(n) + (k − 1)ℓ
≤ ν_{p}(n) + ν_{p}(s) = ν_{p}(ns) = ν_{p}(r).

Case 2: Suppose p ∤ B_{n}. Then p | n and we have ν_{p}(nB_{n}^{k−1}) = ν_{p}(n) ≤ ν_{p}(r).

Combining all cases, we have nB_{n}^{k−1} | r.

For the converse, we assume that nB_{n}^{k−1} | r. Let p be a prime dividing B_{n}. Let ν_{p}(B_{n}) = ℓ ≥ 1. Then Lemma 12(ii, iii, iv) implies

ν_{p}(B_{r}) ≥ ν_{p}(B_{nB_{n}^{k−1}}) = ν_{p}(B_{n}) + ν_{p}(B_{n}^{k−1})
= ℓ + (k − 1)ℓ = kℓ = ν_{p}(B_{n}^{k}).

Since this is true for all primes p dividing B_{n}, it follows that B_{n}^{k} | B_{r}.

4 Acknowledgments

The authors would like to thank the anonymous referee who provided constructive comments and valuable suggestions that led to the improvement of the quality of this paper. We would also like to thank Brian Hopkins for proofreading the first draft of this paper.

References

[1] P. Filipponi and H. T. Freitag, The Zeckendorf decomposition of certain classes of integers, in G. E. Bergum, A. N. Philippou, and A. F. Horadam, eds., Applications of Fibonacci Numbers, Vol. 6, Springer, 2012, pp. 123–135.

[2] A. Gottschlich, On positive integers n dividing the nth term of an elliptic divisibility sequence, New York J. Math. 18 (2012), 409–420.

[3] T. Lengyel, The order of the Fibonacci and Lucas numbers, Fibonacci Quart. 33 (1995), 234–239.

[4] Y. Matijasevich, Enumerable sets are diophantine, Dokl. Math. 11 (1970), 354–358.

[5] K. Onphaeng and P. Pongsriiam, Exact divisibility by powers of the integers in the Lucas sequence of the first kind, AIMS Math. 5 (2020), 6739–6748.

[6] C. Panraksa and A. Tangboonduangjit, On some arithmetic properties of a sequence related to the quotient of Fibonacci numbers, Fibonacci Quart. 55 (2017), 21–28.

[7] C. Panraksa and A. Tangboonduangjit, p-Adic valuation of Lucas iteration sequences, Fibonacci Quart. 56 (2018), 348–353.

[8] J. Reynolds, Perfect powers in elliptic divisibility sequences, J. Number Theory 132 (2012), 998–1015.

[9] C. Sanna, The p-adic valuation of Lucas sequences, Fibonacci Quart. 54 (2016), 118– 124.

[10] J. H. Silverman and K. Stange, Terms in elliptic divisibility sequences divisible by their indices, Acta Arith. 146 (2011), 355–378.

[11] J. H. Silverman and J. T. Tate, Rational Points on Elliptic Curves, Springer, 2015.

[12] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2022. Available

at https://oeis.org.

[13] K. E. Stange, The Tate pairing via elliptic nets, in International Conference on Pairing-Based Cryptography, Springer, 2007, pp. 329–348.

[14] M. Ward, Memoir on elliptic divisibility sequences, Amer. J. Math. 70 (1948), 31–74.

[15] M. Verzobio, A recurrence relation for elliptic divisibility sequences, preprint, 2021.

Available at https://arxiv.org/abs/2102.07573.

2020 Mathematics Subject Classification: Primary 11B39; Secondary 11B83. Keywords: Fibonacci number, Lucas number, elliptic divisibility sequence, strong divisibility sequence, almost strong divisibility sequence, Matijasevich, Hilbert’s tenth problem.

(Concerned with sequences \underline{A000045}, \underline{A000225}, \underline{A006769}, and \underline{A088545}.)

Received May 16 2022; revised versions received July 31 2022; August 7 2022. Published in Journal of Integer Sequences, October 28 2022.

Return to Journal of Integer Sequences home page.