The Greatest Common Divisor of Two Recursive Functions

Jan-Christoph Schlage-Puchta and Jürgen Spilker Mathematisches Institut Eckerstr. 1 79104 Freiburg Germany

                   jcp@math.uni-freiburg.de
             Juergen.Spilker@math.uni-freiburg.de

Abstract

Let g, h be solutions of a linear recurrence relation of length 2. We show that under some mild assumptions the greatest common divisor of g(n) and h(n) is periodic as a function of n and compute its mean value.

1. Problems and Results

Let a, b be coprime integers, b ≠ 0, and consider the recurrence relation

f(n + 2) = af(n + 1) + bf(n), n ∈ ℕ_{0}. (1)

Let g, h : ℕ_{0} → ℤ be solutions of (1) with

|g(n)| + |h(n)| > 0  (2)

for all n ∈ ℕ_{0}. We define the gcd function t(n) = gcd(g(n), h(n)) and consider two problems. Problem 1. Under which conditions on g and h is the function t(n) periodic? Problem 2. If t(n) is periodic, what is the mean value of t(n)?

We first need a Definition. We call a function f : ℕ_{0} → ℤ periodic and q ∈ ℕ a period of f, iff there exists some n_{0} ∈ ℕ_{0} such that f(n) = f(n + q) for all n ≥ n_{0}. If one can choose n_{0} = 0, f is called simply periodic.

In this note we prove the following two theorems.

Theorem 1. Let g, h : ℕ_{0} → ℤ be solutions of (1) satisfying (2), and assume that c := g(1)h(0) − g(0)h(1) ≠ 0. Then

(a) the function t(n) is periodic, moreover, if gcd(b, c) = 1, it is simply periodic;

(b) every common period of g(n) mod |c| and h(n) mod |c| is a period of t(n);

(c) for all n ∈ ℕ_{0} we have t(n) | c.

Theorem 2. Let g, h : ℕ_{0} → ℤ be solutions of (1) satisfying (2), and assume that g(0) = 0, g(1) = 1, c := h(0) ≠ 0 and gcd(b, c) = 1. Then the mean value of t(n)equals ∑_{d | c} \frac{φ(d)}{k(d)}, where k(d) := min{n ∈ ℕ : d | g(n)}.

Examples. 1. In the case g(0) = 0, g(1) = 1, h(0) = 2, h(1) = a, McDaniel [1] has shown, that t(n) is 1 or 2 for n ∈ ℕ. This follows also from our Theorem 1 (c). If further a = b = 1, we obtain the Fibonacci function (resp., Lucas function). Since g(n) mod 2 and h(n) mod 2 are simply periodic with period 3, we get

t(n) = \{ \begin{matrix}2, & n ≡ 0 (mod 3); \\ 1, & n ≢ 0 (mod 3), \end{matrix}

with mean value \frac{4}{3}. This is a well-known result (see e.g., [2], [3]).

2. Defining g and h by a = 1, b = 2, g(0) = h(0) = 1, g(1) = 2, h(1) = 0, we obtain the gcd function

t(n) = \{ \begin{matrix}1, & n = 0 \\ 2, & n ≥ 1 \end{matrix} ,

which is periodic, but not simply periodic.

Remarks. 1. The assumption gcd(a, b) = 1 in Theorem 1 is necessary, since for every common divisor d of a and b we have

d^{n} | t(2n), n ∈ ℕ.

If d > 1, t(n) is unbounded, hence not periodic.

2. The gcd functions of recurrences of higher order need not be periodic. The companion polynomial (x − 1)(x − 2)(x − 3) corresponds to

f(n + 3) = 6f(n + 2) − 11f(n + 1) + 6f(n), n ∈ ℕ_{0}.

It has solutions g(n) = 2^{n+1} − 1 and h(n) = 3^{n+1} − 1 with c = −2. If p ≥ 5 is a prime, and n ≡ −1 (mod p − 1), then

t(n) = gcd(2^{n+1} − 1, 3^{n+1} − 1) ≡ 0 (mod p)

and t(n) ≥ p; hence, t(n) is not bounded and a forteriori not periodic.

3. The function ℓ(d) does not depend on the period q of t(n) mod d. If f(n) is the solution of (1) with initial values f(0) = 0, f(1) = 1 (the generalized Fibonacci function), one can take any period q of f(n) mod d: We have

g(n) = (g(1) − ag(0))f(n) + g(0)f(n + 1), n ∈ ℕ_{0},

hence, q is a period of g(n) mod d, and similarly for h(n) mod d, thus q is a period of t(n) mod d, too.

4. The mean value M of t(n) depends only on the determinant c of the initial values of g and h. It is unbounded as a function of m = |c|, even if g(0) = 0, g(1) = 1, since k(d) ≤ d4^{ω(d)} (see [3]) implies

M ≥ ∑_{d | m} \frac{φ(d)}{d4^{ω(d)}} = ∏_{p^{j}∥m} (1 + \frac{p − 1}{4p}j) ≥ (\frac{9}{8})^{ω(m)}

5. The assumption gcd(b, c) = 1 in Theorem 2 is necessary, however, there is always some n_{0} such that the function t̃(n) = t(n + n_{0}) has the same mean value as t(n) and the mean value formula holds true for t̃.

2. Proofs

We first need two lemmas, which are well-known for the classical Fibonacci function (see [2]).

Lemma 1. Let f : ℕ_{0} → ℤ be a solution of (1), and d ∈ ℕ. Then the function n ↦ f(n) mod d is periodic, and simply periodic if gcd(b, d) = 1.

Proof. There are positive integers n_{1} < n_{2}, such that both f(n_{1}) ≡ f(n_{2}) (mod d) and f(n_{1} + 1) ≡ f(n_{2} + 1) (mod d). Then q = n_{2} − n_{1} is a period of f(n) mod d, since by (1), f(n + q) ≡ f(n) (mod d) for all n ≥ n_{1}. Assume that f(n_{0} + q) ≢ f(n_{0}) (mod d), and choose n_{0} maximal with this property. Then by (1), we have mod d the congruences

bf(n_{0}) = f(n_{0} + 2) − af(n_{0} + 1)
≡ f(n_{0} + q + 2) − af(n_{0} + q + 1)
= bf(n_{0} + q).

If gcd(b, d) = 1, this gives the contradiction f(n_{0}) ≡ f(n_{0} + q) (mod d). □

Lemma 2. Let f : ℕ_{0} → ℤ be the generalized Fibonacci solution of (1), i.e., f(0) = 0, f(1) = 1. Then

(a) gcd(f(n), f(n + 1)) = 1, n ∈ ℕ_{0};

(b) f(m + n) = f(m + 1)f(n) + bf(m)f(n − 1), m ∈ ℕ_{0}, n ∈ ℕ;

(c) if d, n ∈ ℕ, and k(d) = min{n ∈ ℕ : d | f(n)}, then (d | f(n) ⇔ k(d) | n).

Proof. (a). Let p be a prime, and n be the least integer with p | f(n), p | f(n+1); in particular, n > 1. The equation f(n+1) = af(n)+bf(n−1) implies p | bf(n−1), hence, p | b. Similarly, f(n) = af(n−1)+bf(n−2) implies p | af(n−1), thus p | a. This contradicts the assumption gcd(a, b) = 1.

(b). This follows by induction on n.

(c). Let L := {n ∈ ℕ_{0} : d | f(n)}. If m, n ∈ L, we get m + n ∈ L by (b)., and if m > n, we have f(m) = f(m−n)f(n+1)+bf(m−n−1)f(n), hence, d | f(m−n)f(n+1), so m−n ∈ L by (a). Take n ∈ L and write n = mk(d) + t with 0 ≤ t < k(d). Since t = n − mk(d) ∈ L, we have t = 0 and L = k(d) · ℕ_{0}. This proves the last claim. □

Proof of Theorem 1. Let f : ℕ_{0} → ℤ be the solution of (1) with initial values f(0) = 0, f(1) = 1. We have

cf(n) = h(0)g(n) − g(0)h(n),  n ∈ ℕ_{0},  (3)

since both sides solve (1), and the initial values are 0 and c. Similarly,

cf(n + 1) = (ah(0) − h(1))g(n) − (ag(0) − g(1))h(n),  n ∈ ℕ_{0}.  (4)

Fix n ∈ ℕ_{0} and let t be a common divisor of g(n) and h(n). Then t | c(f(n), f(n + 1)) by (3) and (4), hence t | c by Lemma 2 (a) From this we deduce

t(n) | c,  for all n ∈ ℕ_{0}.  (5)

By Lemma 1, a common period q of g(n) mod |c| and h(n) mod |c| exists, so, by (5),

t(n) = gcd(g(n), h(n), c) = gcd(g(n + q), h(n + q), c) = t(n + q), if n ≥ n_{0}.

This proves Theorem 1. □

Proof of Theorem 2. Set m := |c|, and let q be a period of t(n) mod m, which exists by Lemma 1. Then, since t is simply periodic, the mean value of t(n) is

M = \frac{1}{q} ∑_{1≤n≤q} t(n),

and by Theorem 1 (c), this quantity is equal to \frac{1}{q} ∑_{d | m} dℓ(d), where ℓ(d) = #\{n ≤ q : gcd(t(n), m) = d}. Further, we have

M = \frac{1}{q} ∑_{1≤n≤q} gcd(t(n), m) = \frac{1}{q} ∑_{s | m} s ( ∑_{{1≤n≤q \atop gcd(t(n),m)=s}} 1) .

Since

∑_{k | n} μ(k) = \{ \begin{matrix}1, & n = 1 \\ 0, & n > 1 \end{matrix} ,  (6)

the inner sum can be written as

∑_{{1≤n≤q \atop s | t(n)}} ∑_{k | gcd(t(n)/s,m/s)} μ(k) = ∑_{k | \frac{m}{s}} (μ(k) ∑_{{1≤n≤q \atop sk | t(n)}} 1) .

Set d := sk; then

M = ∑_{d | m} (ℓ(d) ∑_{k | d} μ(k)\frac{d}{k}) .

We use ∑_{d | n} φ(d) = n together with (6) and see ∑_{k | d} μ(k)\frac{d}{k} = φ(d). Hence,

M = \frac{1}{q} ∑_{d | m} φ(d)#\{n ≤ q : d | t(n)\}

Since g(0) = 0, g(1) = 1, we have

h(n) = (h(1) − ah(0))g(n) + h(0)g(n + 1),

and by Lemma 2 (a), we obtain

t(n) = gcd(g(n), h(0)g(n + 1)) = gcd(g(n), h(0)) = gcd(g(n), m).

We finally get by Lemma 2 (c) for every d | m

#\{n ≤ q : d | t(n)\} = ∑_{{1≤n≤q \atop d | g(n)}} 1 = ∑_{{1≤n≤q \atop k(d) | n}} 1 = \frac{q}{k(d)},

and Theorem 2 is proven. □

References

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

[2] V. E. Hoggatt, Fibonacci and Lucas numbers, Boston etc.: Houghton Mifflin Company IV, 1969.

[3] D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly 67 (1960), 525–532.

2000 Mathematics Subject Classification: Primary 11B37; Secondary 11B39, 11A05. Keywords: Greatest common divisor, recursive functions, periodic functions, mean values.

Received October 8 2003; revised version received January 27 2004. Published in Journal of Integer Sequences, February 16 2004.

Return to Journal of Integer Sequences home page.