GCD Property of the Generalized Star of David in the Generalized Hosoya Triangle

Rigoberto Flórez

Department of Mathematics and Computer Science

The Citadel Charleston, SC 29409

USA

rigo.florez@citadel.edu

Robinson A. Higuita Departamento de Matemáticas

Universidad de Antioquia Medellín Colombia

robinharra@yahoo.es

Leandro Junes

Department of Mathematics, Computer Science and Information Systems

California University of Pennsylvania

California, PA 15419

USA

junes@calu.edu

Abstract

The generalized Hosoya triangle is an arrangement of numbers in which each entry is a product of two generalized Fibonacci numbers. We prove the GCD property for the star of David of length two. We give necessary and sufficient conditions such that the star of David of length three satisfies the GCD property. We propose some open questions and a conjecture for the star of David of length bigger than or equal to four. We also study GCD properties and modularity properties of generalized Fibonacci numbers.

1 Introduction

The nth generalized Fibonacci number is a linear combination of the elements F_{n−2} and F_{n−1} with integer coefficients. That is, if we take two integers a and b, then the first and second generalized Fibonacci numbers are a and b, respectively, and the nth generalized Fibonacci number has the form aF_{n−2} + bF_{n−1}, where n > 2. If a = b = 1, then we obtain the nth regular Fibonacci number.

The generalized Hosoya triangle is a triangular arrangement of numbers that resembles the Pascal triangle. Each entry is the product of two generalized Fibonacci numbers instead of a binomial coefficient. In particular, the regular Hosoya triangle [5, 7] consists of a triangular array of numbers where each entry is the product of two Fibonacci numbers. Hosoya [5] published this triangle in 1976.

Several authors have studied greatest common divisor (GCD) properties of some geometric configurations in the Pascal triangle and the regular Hosoya triangle (see, for example, [1, 2, 3, 4, 6, 8]). We study GCD properties of a special configuration of points in the generalized Hosoya triangle called the generalized star of David (GSD). We form a GSD by the vertices of two triangles from a regular hexagon in a generalized Hosoya triangle. We say that a star of David has length l if a side of the regular hexagon has length l.

Many authors have studied properties of the star of David of length two and/or its generalizations (see, for example [1, 2, 3, 4, 6, 8]). With the exception of the work done by Flórez and Junes [1] all these papers consider the star of David in the Pascal triangle.

Hoggatt and Hansell [4] proved that the product of all points in a star of David of length two in the Pascal triangle forms a perfect square. Hillman and Hogart [3] proved that the GCD of each triangle of the star of David of length two in the Pascal triangle gives the same number. These two properties are called the product and GCD properties, respectively, of the star of David. Flórez and Junes [1] proved that both properties are true for any star of David of length two in the regular Hosoya triangle.

We prove the GCD property of the star of David of length two in the generalized Hosoya triangle. We give necessary and sufficient conditions such that the star of David of length three in the generalized Hosoya triangle satisfies the GCD property. These conditions depend on L_{2}–divisibility, where L_{2} is the second Lucas number. To prove these results, we introduce new properties of generalized Fibonacci numbers. In particular, we provide an analog to the identity gcd(F_{n}, F_{m}) = F_{gcd(n,m)} for generalized Fibonacci numbers and show that if a generalized Fibonacci number G_{n} is divisible by F_{w}, then the GCD of G_{n} and G_{n+kw} is F_{w} for any non–zero integer k.

We propose a conjecture that gives necessary and sufficient conditions to determine whether the star of David of length l ≥ 4 has the GCD property. These conditions depend on L_{l−1}–divisibility, where L_{l−1} is the (l − 1)th Lucas number.

2 Preliminaries and Examples

In this section we give some examples and introduce notation and definitions that we are going to use throughout the paper. Some of them are well known, but we prefer to restate them here to avoid ambiguities.

2.1 The Generalized Hosoya Triangle

We denote by {G_{n}(a, b)}_{n∈ℕ} the generalized Fibonacci sequence with integers a and b. That is,

G_{1}(a, b) = a, G_{2}(a, b) = b and G_{n}(a, b) = G_{n−1}(a, b) + G_{n−2}(a, b) for all n ∈ ℕ \ {1, 2}.

It is clear that G_{n}(1, 1) = F_{n}. When there is no ambiguity with a and b, we denote the nth term of the generalized Fibonacci sequence by G_{n} instead of G_{n}(a, b). The first eight terms of the generalized Fibonacci sequence with integers a and b are

a, b, a + b, a + 2b, 2a + 3b, 3a + 5b, 5a + 8b, and 8a + 13b.

Notice that every element in this sequence is a linear combination of the integers a and b with Fibonacci coefficients. In general, we have that G_{n} = a F_{n−2} + b F_{n−1} for all n ∈ ℕ (see, for example, [7, Thm. 7.1, p. 109].)

The generalized Hosoya sequence {H_{a,b}(r, k)}_{r≥k≥1} is defined by the double recursion

H_{a,b}(r, k) = H_{a,b}(r − 1, k) + H_{a,b}(r − 2, k)

and

H_{a,b}(r, k) = H_{a,b}(r − 1, k − 1) + H_{a,b}(r − 2, k − 2)

where r > 2 and 1 ≤ k ≤ r, with initial conditions

H_{a,b}(1, 1) = a^{2}; H_{a,b}(2, 1) = ab; H_{a,b}(2, 2) = ab; H_{a,b}(3, 2) = b^{2}.

It is easy to see that if we let a = b = 1 in the generalized Hosoya sequence, then we obtain the regular Hosoya sequence {H(r, k)}_{r≥k≥1} as Koshy defines it [7, pp. 187–188]. It is known that

H(r, k) = F_{k} F_{r−k+1}

for all natural numbers r, k such that k ≤ r, see [7, p. 188]. This and Proposition 1 show that our definition of {H_{a,b}(r, k)}_{r≥k≥1} is the “right” generalization for {H(r, k)}_{r≥k≥1}.

Proposition 1. If r and k are natural numbers such that k ≤ r, then

H_{a,b}(r, k) = G_{k} G_{r−k+1},

for all integers a, b ∈ ℤ.

Proof. We prove first that H_{a,b}(r, 1) = a G_{r} for all r ∈ ℕ.

Since H_{a,b}(r, 1) = H_{a,b}(r − 1, 1) + H_{a,b}(r − 2, 1) for all r ≥ 3, where H_{a,b}(1, 1) = a^{2} and H_{a,b}(2, 1) = ab, a straightforward argument by strong induction on r shows that

H_{a,b}(r, 1) = a G_{r} for all r ∈ ℕ.  (a)

Using a similar argument, we can prove that

H_{a,b}(r, 2) = b G_{r−1} for all r ∈ ℕ \ {1}.  (b)

Now, for any k ∈ ℕ let P (k) be the statement: H_{a,b}(r, k) = G_{k} G_{r−k+1} for all natural numbers r such that r ≥ k. We want to prove by strong induction that P (k) is true for all k ∈ ℕ.

Statements (a) and (b) show that P (1) and P (2) are true. This proves the basis step. We assume now that P (1), …, P (k) are true for a fixed natural number k ≥ 2 and prove that P (k + 1) is true. Let r be a natural number such that r ≥ k + 1. Therefore, r − 1 ≥ k and r − 2 ≥ k − 1. Since P (k − 1) and P (k) are true, we can write

H_{a,b}(r − 2, k − 1) = G_{k−1} G_{r−k} and H_{a,b}(r − 1, k) = G_{k} G_{r−k}.

This and the recurrence H_{a,b}(r, k + 1) = H_{a,b}(r − 1, k) + H_{a,b}(r − 2, k − 1) show that

H_{a,b}(r, k + 1) = G_{k+1} G_{r−k}.

Thus, P (k + 1) is true. This proves the proposition.

If there is no ambiguity with the integers a and b we write H(r, k) instead of H_{a,b}(r, k). The generalized Hosoya sequence gives rise to the generalized Hosoya triangle where the entry in position k, taken from left to right, of the rth row is equal to H(r, k) (see Table 1).

H(1, 1)
H(2, 1)  H(2, 2)
H(3, 1)  H(3, 2)  H(3, 3)
H(4, 1)  H(4, 2)  H(4, 3)  H(4, 4)
H(5, 1)  H(5, 2)  H(5, 3)  H(5, 4)  H(5, 5)
H(6, 1)  H(6, 2)  H(6, 3)  H(6, 4)  H(6, 5)  H(6, 6)

Table 1: Generalized Hosoya Triangle.

If P is a point in a generalized Hosoya triangle, then it is clear that there are two unique positive integers r and k such that r ≥ k with P = H(r, k). We call the pair (r, k) the rectangular coordinates of the point P.

We now give a more convenient system of coordinates for points in the generalized Hosoya triangle. Proposition 1 shows that every entry of the generalized Hosoya triangle is the product of two generalized Fibonacci numbers. In particular, if we use Proposition 1 for all entries of Table 1, we obtain Table 2.

G_{1} G_{1}
G_{1} G_{2}  G_{2} G_{1}
G_{1} G_{3}  G_{2} G_{2}  G_{3} G_{1}
G_{1} G_{4}  G_{2} G_{3}  G_{3} G_{2}  G_{4} G_{1}
G_{1} G_{5}  G_{2} G_{4}  G_{3} G_{3}  G_{4} G_{2}  G_{5} G_{1}
G_{1} G_{6}  G_{2} G_{5}  G_{3} G_{4}  G_{4} G_{3}  G_{5} G_{2}  G_{6} G_{1}

Table 2: Generalized Hosoya Triangle.

Notice that any diagonal of Table 2 is the collection of all generalized Fibonacci numbers multiplied by a particular G_{n}. More precisely, an nth diagonal in the generalized Hosoya triangle is the collection of all generalized Fibonacci numbers multiplied by G_{n}. We distinguish between slash diagonals and backslash diagonals, with the obvious meaning. We write S(G_{n}) and B(G_{m}) to mean the slash diagonal and backslash diagonal, respectively (see Figure 1). We formally define these two diagonals as

S(G_{n}) = {H(n + i − 1, n)}_{i=1}^{∞} = {G_{n} G_{i}|i ∈ ℕ},

and

B(G_{m}) = {H(m + i − 1, i)}_{i=1}^{∞} = {G_{i} G_{m}|i ∈ ℕ}.

Figure 1: The slash diagonal S(G_{3}) and backslash diagonal B(G_{4}).

We can associate an ordered pair of natural numbers to every element of a generalized Hosoya triangle. If P is a point in a generalized Hosoya triangle, then there are two generalized Fibonacci numbers G_{m} and G_{n} such that P ∈ B(G_{m}) ∩ S(G_{n}) (Figure 1 depicts this fact for m = 4 and n = 3.) Thus, P = G_{m} G_{n}. Therefore, the point P corresponds to the pair (m, n). It is clear that this correspondence is a bijection between points of a generalized Hosoya triangle and ordered pairs of natural numbers. The pair (m, n) is called the diagonal coordinate of P. Thus, we can view Proposition 1 as a way to change from rectangular coordinates to diagonal coordinates and vice–versa.

Throughout this paper we use only diagonal coordinates to refer to any point in a generalized Hosoya triangle.

We now give some examples of generalized Hosoya triangles. We can construct different triangles by fixing values for the integers a and b. For the first example we fix a = b = 1 and obtain the following numerical sequence.

G_{1} = 1, G_{2} = 1, G_{3} = 2, G_{4} = 3, G_{5} = 5, G_{6} = 8, …

Substituting these values in Table 2 we obtain the regular Hosoya triangle (see [5, 7] and Table 3).

1

1  1
2  1  2
3  2  2  3
5  3  4  3  5
8  5  6  6  5  8

Table 3: Regular Hosoya Triangle.

We now fix a = 7 and b = 2 and obtain the following numerical sequence.

G_{1} = 7, G_{2} = 2, G_{3} = 9, G_{4} = 11, G_{5} = 20, G_{6} = 31, …

Substituting these values in Table 2 we obtain a Hosoya triangle with a = 7 and b = 2 (see Table 4 part (a)). Similarly, if we fix a = 5 and b = 8 we obtain another numerical sequence.

G_{1} = 5, G_{2} = 8, G_{3} = 13, G_{4} = 21, G_{5} = 34, G_{6} = 55, …

The Hosoya triangle generated by this new sequence is depicted in Table 4 part (b).

49  25
14  14  40  40
63  4  63  65  64  65
77  18  18  77  105  104  104  105
140  22  81  22  140  170  168  169  168  170
217  40  99  99  40  217 275  272  273  273  272  275
(a)  (b)

Table 4: Generalized Hosoya triangles.

2.2 Generalized Star of David

Let E be a regular hexagon formed with points lying in a generalized Hosoya triangle. We say that E has length l if a side of the hexagon contains l points from the generalized Hosoya triangle. We denote the corner points of E by a_{1}, a_{2}, a_{3} and b_{1}, b_{2}, b_{3}. The star of David of length l is a configuration formed by the six corner points of E. That is, the star of David is a configuration of six points in the Hosoya triangle formed by two triangles with vertices a_{1}, a_{2}, a_{3} and b_{1}, b_{2}, b_{3} of E. Figure 2 part (a) represents a star of David of length two. The continuous lines in Figure 2 parts (b) and (c) show stars of David of length three and four, respectively.

Figure 2: Stars of David.

We first consider some examples of the generalized star of David of length two as in Figure 2 part (a). We can obtain a complete characterization of its vertices a_{1}, a_{2}, a_{3} and b_{1}, b_{2}, b_{3}, by knowing the location of one. For instance, if (m, n) are the diagonal coordinates of a_{2}, then we have

\begin{matrix}a_{1} = G_{m+1} G_{n−2}, & a_{2} = G_{m} G_{n} & and & a_{3} = G_{m+2} G_{n−1}, \\ b_{1} = G_{m} G_{n−1}, & b_{2} = G_{m+2} G_{n−2} & and & b_{3} = G_{m+1} G_{n}. \end{matrix}

We need to give values to a, b, m and n to consider some particular examples. For instance, if we take a = b = 1 (the regular Hosoya triangle) and m = 5, n = 4, then we obtain

a_{1} = 8, a_{2} = 15, a_{3} = 26, b_{1} = 10, b_{2} = 13, b_{3} = 24.

Similarly, if we take a = 7, b = 2 (generalized Hosoya triangle in Table 4 part (a)), m = 3 and n = 3, then we obtain

a_{1} = 77, a_{2} = 81, a_{3} = 40, b_{1} = 18, b_{2} = 140, b_{3} = 99.

If we now take a = 5, b = 8 (generalized Hosoya triangle in Table 4 part (b)), m = 2 and n = 4, then we have

a_{1} = 104, a_{2} = 168, a_{3} = 273, b_{1} = 104, b_{2} = 168, b_{3} = 273.

Notice that in all three cases gcd(a_{1}, a_{2}, a_{3}) = gcd(b_{1}, b_{2}, b_{3}) = 1. Flórez and Junes proved in [1, Thm. 3.2] that this is always true for any star of David of length two in the regular Hosoya triangle. We prove a more general result. Namely, we show that gcd(a_{1}, a_{2}, a_{3}) = gcd(b_{1}, b_{2}, b_{3}) = (gcd(a, b))^{2} for any star of David of length two in any generalized Hosoya triangle (see Theorem 9).

We now consider some examples of the generalized star of David of length three as in Figure 2 part (b). We can obtain a complete characterization of its vertices a_{1}, a_{2}, a_{3} and b_{1}, b_{2}, b_{3} by knowing the location of one. For instance, if (m, n) are the diagonal coordinates of a_{2}, then we have

\begin{matrix}a_{1} = G_{m+2} G_{n−4}, & a_{2} = G_{m} G_{n} & and & a_{3} = G_{m+4} G_{n−2}, \\ b_{1} = G_{m} G_{n−2}, & b_{2} = G_{m+4} G_{n−4} & and & b_{3} = G_{m+2} G_{n}. \end{matrix}

We also need to give values to a, b, m and n to consider some particular examples. If we take a = b = 1 (the regular Hosoya triangle) and m = 3, n = 5, then we get

a_{1} = 5, a_{2} = 10, a_{3} = 26, b_{1} = 4, b_{2} = 13, b_{3} = 25.

Therefore, gcd(a_{1}, a_{2}, a_{3}) = gcd(b_{1}, b_{2}, b_{3}) = 1. However, if we take m = 8 and n = 16, then

a_{1} = 7920, a_{2} = 20727, a_{3} = 54288, b_{1} = 7917, b_{2} = 20736, b_{3} = 54285,

gcd(a_{1}, a_{2}, a_{3}) = 9 and gcd(b_{1}, b_{2}, b_{3}) = 3. In this case gcd(a_{1}, a_{2}, a_{3}) ≠ gcd(b_{1}, b_{2}, b_{3}). We give in this paper a complete characterization of all stars of David of length three in the generalized Hosoya triangle for which gcd(a_{1}, a_{2}, a_{3}) = gcd(b_{1}, b_{2}, b_{3}) (see Theorem 12).

We can construct similar examples for the star of David of length four. In general, if (m, n) are the diagonal coordinates of a_{2}, then the vertices of the star of David of length l in the generalized Hosoya triangle are given by

\begin{matrix}a_{1} = G_{m+(l−1)} G_{n−2(l−1)}, & a_{2} = G_{m} G_{n} & and & a_{3} = G_{m+2(l−1)} G_{n−(l−1)}, \\ b_{1} = G_{m} G_{n−(l−1)}, & b_{2} = G_{m+2(l−1)} G_{n−2(l−1)} & and & b_{3} = G_{m+(l−1)} G_{n}, \end{matrix}

for positive integers m and n such that n > 2(l − 1). We require that n > 2(l − 1) so that a_{1}, a_{3}, b_{1} and b_{2} correspond to “real” points in the generalized Hosoya triangle.

We finish this subsection with a definition. We say that a star of David of length l has the GCD property if gcd(a_{1}, a_{2}, a_{3}) = gcd(b_{1}, b_{2}, b_{3}).

2.3 Auxiliary Results

The multiplication property of the GCD says that if a and b are co–prime, then gcd(ab, c) = gcd(a, c) gcd(b, c). We use this property to prove Lemma 8, which plays a special role in the proof of the main results, Theorems 9 and 12. In addition, we also use the following proposition.

Proposition 2 ([1, Proposition 2.2]). If gcd(a, c) = gcd(b, d) = 1, then gcd(ab, cd) = gcd(a, d) gcd(b, c), where a, b, c, d ∈ ℤ.

3 GCD Properties of Generalized Fibonacci Numbers

In this section we study GCD properties of generalized Fibonacci numbers as well as some of its modularity properties. In particular, we provide an analog to the identity gcd(F_{n}, F_{m}) = F_{gcd(n,m)} for generalized Fibonacci numbers. That is, gcd(G_{n}, G_{m}) is always a divisor of gcd(a, b) F_{|m−n|} with equality when |m − n| ∈ {1, 2}. We also prove that if a generalized Fibonacci number G_{n} is divisible by F_{w}, then the GCD of G_{n} and G_{n+kw} is F_{w} for any non–zero integer k.

We use these results to prove the GCD property for the star of David of length two and three in the generalized Hosoya triangle. We write a | b to mean that a divides b.

Lemma 3. If gcd(a, b) = d, a′ = a/d and b′ = b/d, then G_{n}(a, b) = dG_{n}(a′, b′) for n ∈ ℕ.

Proof. We know that G_{n}(a, b) = aF_{n−2} + bF_{n−1} for all n ∈ ℕ. Thus,

G_{n}(a, b) = da′F_{n−2} + db′F_{n−1} = d(a′F_{n−2} + b′F_{n−1}) = dG_{n}(a′, b′).

This proves the Lemma.

Recall that we use G_{m} for G_{m}(a, b) for any integer m if there is no ambiguity. Similarly, we use G′_{m} for G_{m}(a′, b′) if d = gcd(a, b), a′ = a/d and b′ = b/d.

Lemma 4. If a, b, n and w are integers, then

G_{n+w}(a, b) = (aF_{w−1} + bF_{w})F_{n−2} + (aF_{w} + bF_{w+1})F_{n−1} = G_{n} (G_{w+1}, G_{w+2}) .

Proof. It is well known that F_{n+m} = F_{n−1}F_{m} + F_{n}F_{m+1}, see [7, Ex. 47, p. 89]. Thus,

G_{n+w}(a, b) = aF_{w+n−2} + bF_{n−1+w}
= a(F_{w−1}F_{n−2} + F_{w}F_{n−1}) + b(F_{n−2}F_{w} + F_{n−1}F_{w+1})
= (aF_{w−1} + bF_{w})F_{n−2} + (aF_{w} + bF_{w+1})F_{n−1}
= G_{w+1}F_{n−2} + G_{w+2}F_{n−1}
= G_{n} (G_{w+1}, G_{w+2}) .

This proves the lemma.

Theorem 5. Let d = gcd(a, b). If n and w are natural numbers, then gcd(G_{n}, G_{n+w}) | d F_{w}. Moreover, if w = 1, 2, then gcd(G_{n}, G_{n+w}) = d.

Proof. The Lemma 3 implies that gcd(G_{n}, G_{n+w}) = d gcd(G′_{n}, G′_{n+w}). Thus, it is enough to prove the theorem for gcd(G′_{n}, G′_{n+w}).

We first prove that gcd(G′_{n}, G′_{n+1}) = 1. We use induction on n. If n = 1, then

gcd(G′_{1}, G′_{2}) = gcd(a′, b′) = 1.

This proves the basis step. We now suppose that gcd(G′_{k}, G′_{k+1}) = 1 for a fixed natural number k and prove gcd(G′_{k+1}, G′_{k+2}) = 1.

Let r be the natural number such that gcd(G′_{k+1}, G′_{k+2}) = r. Thus,

r | G′_{k+1} and r | G′_{k+2}.  (1)

Therefore, r | (G′_{k+2} − G′_{k+1}). Thus, r | G′_{k}. This and (1) imply that r | gcd(G′_{k}, G′_{k+1}). Therefore, the inductive hypothesis implies that r = 1. This proves that

gcd(G′_{n}, G′_{n+1}) = 1 for every n ∈ ℕ.  (2)

We now prove that gcd(G′_{n}, G′_{n+w}) divides F_{w}. Let d′ be a divisor of gcd(G′_{n}, G′_{n+w}). Therefore,

d′ | G′_{n} and d′ | G′_{n+w}.  (3)

So, d′ divides any linear combination of G′_{n} and G′_{n+w}. In particular,

d′ | (G′_{n+w} − F_{w−1}G′_{n}).  (4)

We prove that d′ | F_{w}G′_{n+1}. Since G′_{k} = G_{k}(a′, b′) for any positive integer k, from Lemma 4 we have

G′_{n+w} = (a′F_{w−1} + b′F_{w})F_{n−2} + (a′F_{w} + b′F_{w+1})F_{n−1}.

Therefore,

G′_{n+w} − F_{w−1}G′_{n} = [(a′F_{w−1} + b′F_{w})F_{n−2} + (a′F_{w} + b′F_{w+1})F_{n−1}] − F_{w−1}(a′F_{n−2} + b′F_{n−1}).

That is,

G′_{n+w} − F_{w−1}G′_{n} = b′F_{w}F_{n−2} + (a′F_{w} + b′(F_{w+1} − F_{w−1}))F_{n−1}
= b′F_{w}F_{n−2} + (a′F_{w} + b′F_{w})F_{n−1}
= F_{w}(a′F_{n−1} + b′(F_{n−2} + F_{n−1}))
= F_{w}(a′F_{n−1} + b′F_{n})
= F_{w}G′_{n+1}.

This and (4) imply that d′ | F_{w}G′_{n+1}. From (2) and (3) we have that gcd(d′, G′_{n+1}) = 1. This and d′ | F_{w}G′_{n+1} imply that d′ | F_{w}. We have shown that any divisor of gcd(G′_{n}, G′_{n+w}) is a divisor of F_{w}. This proves that gcd(G′_{n}, G′_{n+w}) divides F_{w}.

We now prove the second claim. Equality (2) proves the second claim for w = 1. If w = 2, then gcd(G′_{n}, G′_{n+2}) divides F_{2}. Therefore, gcd(G′_{n}, G′_{n+2}) = 1 = gcd(a′, b′). This proves the theorem.

Corollary 6. Let m, n, s and t be positive integers. If |m − n| ∈ {1, 2} and |s − t| ∈ {1, 2}, then

gcd(G_{m} G_{s}, G_{n} G_{t}) = gcd(G_{m}, G_{t}) gcd(G_{s}, G_{n}).

Proof. Let d = gcd(a, b), a′ = a/d and b′ = b/d. Since |m − n| ∈ {1, 2} and |s − t| ∈ {1, 2}, Theorem 5 shows that gcd(G′_{m}, G′_{n}) = 1 and gcd(G′_{s}, G′_{t}) = 1. This and Proposition 2 imply that

gcd(G′_{m}G′_{s}, G′_{n}G′_{t}) = gcd(G′_{m}, G′_{t}) gcd(G′_{s}, G′_{n}).

Multiplying both sides of this equality by d^{2} we obtain

d^{2} gcd(G′_{m}G′_{s}, G′_{n}G′_{t}) = d gcd(G′_{m}, G′_{t})d gcd(G′_{s}, G′_{n}).  (5)

Using Lemma 3 one can easily see that

gcd(G_{m}, G_{t}) = d gcd(G′_{m}, G′_{t}),
gcd(G_{s}, G_{n}) = d gcd(G′_{s}, G′_{n}), and
gcd(G_{m} G_{s}, G_{n} G_{t}) = d^{2} gcd(G′_{m}G′_{s}, G′_{n}G′_{t}).

Substituting these three equalities in (5) we obtain that

gcd(G_{m}G_{s}, G_{n}G_{t}) = gcd(G_{m}, G_{t}) gcd(G_{s}, G_{n}).

This proves the corollary.

Theorem 7. Let a, b ∈ ℤ and n, w ∈ ℕ such that gcd(a, b) = 1. Then

G_{n} ≡ 0 (mod F_{w}) if and only if gcd(G_{n}, G_{n−w}) = gcd(G_{n}, G_{n+w}) = F_{w}.

Proof. The proof of necessity is straightforward.

We prove sufficiency. We suppose that G_{n} ≡ 0 (mod F_{w}) and prove that gcd(G_{n}, G_{n−w}) = gcd(G_{n}, G_{n+w}) = F_{w}. Since G_{n} ≡ 0 (mod F_{w}), there is a k ∈ ℤ such that G_{n} = kF_{w}. From Lemma 4 we have that for every m ∈ ℤ

G_{m+w} = (aF_{w−1} + bF_{w})F_{m−2} + (aF_{w} + bF_{w+1})F_{m−1}
= (aF_{w−1} + bF_{w})F_{m−2} + (aF_{w} + b(F_{w−1} + F_{w}))F_{m−1}
= (aF_{m−2} + bF_{m−1})F_{w−1} + F_{w}(bF_{m−2} + aF_{m−1} + bF_{m−1}).

Thus,

G_{m+w} = G_{m}F_{w−1} + F_{w}(bF_{m−2} + aF_{m−1} + bF_{m−1}).  (6)

Taking n instead of m in (6) and using that G_{n} = kF_{w} we obtain

G_{n+w} = kF_{w}F_{w−1} + F_{w}(bF_{n−2} + aF_{n−1} + bF_{n−1})
= F_{w}(kF_{w−1} + (bF_{n−2} + aF_{n−1} + bF_{n−1})).

Therefore, G_{n+w} ≡ 0 (mod F_{w}). Thus, F_{w} | gcd(G_{n+w}, G_{n}). This and Theorem 5 imply that F_{w} = gcd(G_{n+w}, G_{n}). Now, taking n − w instead of m in (6) we obtain

G_{n} = G_{n−w}F_{w−1} + F_{w}(bF_{n−w−2} + aF_{n−w−1} + bF_{n−w−1}).

Since G_{n} = kF_{w}, we have that

G_{n−w}F_{w−1} = kF_{w} − F_{w}(bF_{n−w−2} + aF_{n−w−1} + bF_{n−w−1})
= F_{w}(k − (bF_{n−w−2} + aF_{n−w−1} + bF_{n−w−1})).

This and gcd(F_{w}, F_{w−1}) = 1 imply that G_{n−w} ≡ 0 (mod F_{w}). So, F_{w}| gcd(G_{n−w}, G_{n}). This and Theorem 5 imply that F_{w} = gcd(G_{n−w}, G_{n}), proving sufficiency.

Lemma 8. Let α, β, δ, γ, ρ, ϕ ∈ ℕ and a, b ∈ ℤ such that gcd(a, b) = 1 and let D = gcd (G_{α} G_{β}, G_{δ} G_{γ}, G_{ρ} G_{ϕ}).

1. If α = δ + 1, ρ = δ + 2, β = γ − 2, and ϕ = γ − 1, then D = 1.

2. If δ = α + 1, ρ = α + 2, β = γ − 1, and ϕ = γ − 2, then D = 1.

3. If α = δ + 2, ρ = δ + 4, β = γ − 4, and ϕ = γ − 2, then D = gcd (G_{β}, G_{ρ}, G_{δ}G_{γ}).

4. If δ = α + 2, ρ = α + 4, β = γ − 2, and ϕ = γ − 4, then D = gcd(G_{α}, G_{γ}, G_{ρ}G_{ϕ}).

Proof. It is known that

gcd (G_{α} G_{β}, G_{δ} G_{γ}, G_{ρ} G_{ϕ}) = gcd (gcd(G_{α} G_{β}, G_{δ} G_{γ}), G_{ρ} G_{ϕ})  (7)
= gcd (gcd(G_{α} G_{β}, G_{ρ} G_{ϕ}), G_{δ} G_{γ}) .  (8)

We prove part (1). The proof of part (2) is similar and we omit it. Since |α − δ| = 1 and |β − γ| = 2, Corollary 6 and (7) imply that

D = gcd (gcd(G_{α}, G_{γ}) gcd(G_{δ}, G_{β}), G_{ρ}G_{ϕ}) .  (9)

From Theorem 5, |α − ρ| = 1 and |β − ϕ| = 1, we have gcd(G_{ρ}, G_{α}) = gcd(G_{ϕ}, G_{β}) = 1. Thus,

gcd (gcd(G_{γ}, G_{α}), G_{ρ}) = gcd (gcd(G_{δ}, G_{β}), G_{ϕ}) = 1.

This, Proposition 2 and (9) imply that

D = gcd (gcd(G_{α}, G_{γ}), G_{ϕ}) gcd (gcd(G_{δ}, G_{β}), G_{ρ}) .

Using Theorem 5, |γ − ϕ| = 1 and |δ − ρ| = 2, we have that D = 1. This proves part (1).

We now prove part (3). The proof of part (4) is similar and we omit it. Theorem 5, |α − δ| = 2 and |γ − ϕ| = 2 imply that gcd(G_{α}, G_{δ}) = 1 and gcd(G_{γ}, G_{ϕ}) = 1. Therefore, gcd (gcd(G_{α}, G_{ϕ}), G_{δ}) = 1 and gcd (gcd(G_{α}, G_{ϕ}), G_{γ}) = 1. Thus,

gcd (gcd(G_{α}, G_{ϕ}), G_{δ}G_{γ}) = 1.  (10)

Since |α − ρ| = 2 and |β − ϕ| = 2, Corollary 6 and (8) imply that

D = gcd(gcd(G_{α}, G_{ϕ}) gcd(G_{β}, G_{ρ}), G_{δ}G_{γ}).  (11)

Theorem 5, |α − ρ| = 2 and |β − ϕ| = 2 imply that gcd(G_{α}, G_{ρ}) = gcd(G_{β}, G_{ϕ}) = 1. Therefore, gcd(gcd(G_{α}, G_{ϕ}), gcd(G_{β}, G_{ρ})) = 1. This and the multiplication property of the GCD imply that

gcd (gcd(G_{α}, G_{ϕ}) gcd(G_{β}, G_{ρ}), G_{δ}G_{γ}) = gcd (gcd(G_{α}, G_{ϕ}), G_{δ}G_{γ}) gcd (gcd(G_{β}, G_{ρ}), G_{δ}G_{γ}) .

This, (10) and (11) prove that D = gcd (G_{β}, G_{ρ}, G_{δ}G_{γ}). This proves the lemma.

4 GCD Property for the Star of David of Length Two and Three

In this section we prove the GCD property for the star of David of length two and give necessary and sufficient conditions for the star of David of length three to have the GCD property. We also prove that 9 divides the coordinates of the vertices a_{2} or b_{2} in Figure 2 part (b) if and only if the GCD of each triangle gives distinct numbers.

We remind the reader that if d = gcd(a, b), a′ = a/d and b′ = b/d, then we use G_{m} for G_{m}(a, b) and G′_{m} for G_{m}(a′, b′) for any integer m.

Theorem 9. Let d = gcd(a, b). If a_{1}, a_{2}, a_{3} and b_{1}, b_{2}, b_{3} are the vertices of the star of David of length two, then gcd(a_{1}, a_{2}, a_{3}) = gcd(b_{1}, b_{2}, b_{3}) = d^{2}.

Proof. Let a′ = a/d, b′ = b/d, and (m, n) be the diagonal coordinates of a_{2}. We prove first that gcd(a_{1}, a_{2}, a_{3}) = d^{2}. It is known that a_{1} = G_{m+1} G_{n−2}, a_{2} = G_{m} G_{n} and a_{3} = G_{m+2} G_{n−1}. This and Lemma 3 imply that

gcd(a_{1}, a_{2}, a_{3}) = d^{2} gcd (G′_{m+1} G′_{n−2}, G′_{m} G′_{n}, G′_{m+2} G′_{n−1}) .

This and Lemma 8 part (1) show that gcd(a_{1}, a_{2}, a_{3}) = d^{2}.

The proof of gcd(b_{1}, b_{2}, b_{3}) = d^{2} is analogous to the proof of gcd(a_{1}, a_{2}, a_{3}) = d^{2}. Indeed, the proof follows from Lemma 3 and Lemma 8 part (2). This proves the theorem.

Lemma 10. Let d = gcd(a, b) and a′ = a/d, b′ = b/d. If a_{1}, a_{2}, a_{3} and b_{1}, b_{2}, b_{3} are the vertices of the star of David of length three where (m, n) are the diagonal coordinates of a_{2}, then

1. gcd(a_{1}, a_{2}, a_{3}) = d^{2} gcd(G′_{n−4}, G′_{m+4}, G′_{m}G′_{n}).

2. gcd(b_{1}, b_{2}, b_{3}) = d^{2} gcd(G′_{m}, G′_{n}, G′_{n−4}G′_{m+4}).

Proof. Since (m, n) are the diagonal coordinates of a_{2},

\begin{matrix}a_{1} = G_{m+2} G_{n−4}, & a_{2} = G_{m} G_{n} & and & a_{3} = G_{m+4} G_{n−2}, \\ b_{1} = G_{m} G_{n−2}, & b_{2} = G_{m+4} G_{n−4} & and & b_{3} = G_{m+2} G_{n}. \end{matrix}

This and Lemma 3 imply that

gcd(a_{1}, a_{2}, a_{3}) = d^{2} gcd (G′_{m+2} G′_{n−4}, G′_{m} G′_{n}, G′_{m+4} G′_{n−2}) .

This and Lemma 8 part (3) show that gcd(a_{1}, a_{2}, a_{3}) = d^{2} gcd(G′_{n−4}, G′_{m+4}, G′_{m}G′_{n}). This proves part (1). The proof of part (2) is similar and we omit it.

Theorem 11. Let d = gcd(a, b) and a′ = a/d, b′ = b/d. If a_{1}, a_{2}, a_{3} and b_{1}, b_{2}, b_{3} are the vertices of the star of David of length three where (m, n) are the diagonal coordinates of a_{2}, then

1. G′_{m} ≡ 0 (mod 9) and G′_{n} ≡ 0 (mod 9) if and only if gcd(a_{1}, a_{2}, a_{3}) < gcd(b_{1}, b_{2}, b_{3}).

2. G′_{m+4} ≡ 0 (mod 9) and G′_{n−4} ≡ 0 (mod 9) if and only if gcd(a_{1}, a_{2}, a_{3}) > gcd(b_{1}, b_{2}, b_{3}).

Proof. We prove part (1). For sufficiency, we assume that G′_{m} ≡ 0 (mod 9) and G′_{n} ≡ 0 (mod 9) and prove that gcd(a_{1}, a_{2}, a_{3}) = 3 d^{2} and gcd(b_{1}, b_{2}, b_{3}) = 9 d^{2}.

Since G′_{m} ≡ 0 (mod 9) and G′_{n} ≡ 0 (mod 9), it is clear that G′_{m} ≡ 0 (mod 3) and G′_{n} ≡ 0 (mod 3). This and Theorem 7 imply that

gcd(G′_{m}, G′_{m+4}) = 3 and gcd(G′_{n}, G′_{n−4}) = 3.  (12)

Therefore, 3 | gcd(G′_{n−4}, G′_{m+4}, G′_{m}G′_{n}). We now show that 3 is the only prime divisor of gcd(G′_{n−4}, G′_{m+4}, G′_{m}G′_{n}). If p is a prime number and p | gcd(G′_{n−4}, G′_{m+4}, G′_{m}G′_{n}), then one can easily see that p | gcd(G′_{n−4}, G′_{n}) or p | gcd(G′_{m+4}, G′_{4}). This and (12) imply that p = 3. Thus, gcd(G′_{n−4}, G′_{m+4}, G′_{m}G′_{n}) = 3^{k} for some integer k ≥ 1. We show that k = 1. If k > 1, then 9 | G′_{n−4} and 9 | G′_{m+4}. Since G′_{m} ≡ 0 (mod 9) and G′_{n} ≡ 0 (mod 9), we can conclude that 9 | gcd(G′_{m}, G′_{m+4}) and 9 | gcd(G′_{n}, G′_{n−4}). This contradicts (12). Thus,

gcd(G′_{n−4}, G′_{m+4}, G′_{m}G′_{n}) = 3.  (13)

We now prove that gcd(G′_{m}, G′_{n}, G′_{n−4}G′_{m+4}) = 9. From G′_{m} ≡ 0 (mod 9), G′_{n} ≡ 0 (mod 9) and (12), we can write that 9 | gcd(G′_{m}, G′_{n}, G′_{n−4}G′_{m+4}). We show that 3 is the only prime divisor of gcd(G′_{m}, G′_{n}, G′_{n−4}G′_{m+4}). If p is a prime and p | gcd(G′_{m}, G′_{n}, G′_{n−4}G′_{m+4}), then one can easily see that p | gcd(G′_{n−4}, G′_{n}) or p | gcd(G′_{m+4}, G′_{4}). This and (12) imply that p = 3. Thus, gcd(G′_{m}, G′_{n}, G′_{n−4}G′_{m+4}) = 3^{l} for some integer l ≥ 2. We show that l = 2. If l > 2, then 3^{3} | G′_{n−4}G′_{m+4}. Therefore, 9 | G′_{n−4} or 9 | G′_{m+4}. Since G′_{m} ≡ 0 (mod 9) and G′_{n} ≡ 0 (mod 9), we can conclude that 9 | gcd(G′_{m}, G′_{m+4}) or 9 | gcd(G′_{n}, G′_{n−4}). This contradicts (12). Thus,

gcd(G′_{m}, G′_{n}, G′_{n−4}G′_{m+4}) = 9.

This equality, Lemma 10 and (13) show that gcd(a_{1}, a_{2}, a_{3}) = 3 d^{2} and gcd(b_{1}, b_{2}, b_{3}) = 9 d^{2}, proving sufficiency of part (1).

Conversely, we assume that gcd(a_{1}, a_{2}, a_{3}) < gcd(b_{1}, b_{2}, b_{3}). This and Lemma 10 imply that

gcd(G′_{n−4}, G′_{m+4}, G′_{m}G′_{n}) < gcd(G′_{m}, G′_{n}, G′_{n−4}G′_{m+4}).  (14)

Therefore, gcd(G′_{m}, G′_{n}, G′_{n−4}G′_{m+4}) > 1. If p is a prime such that p | gcd(G′_{m}, G′_{n}, G′_{n−4}G′_{m+4}), then it is easy to see that p | gcd(G′_{m}, G′_{m+4}) or p | gcd(G′_{n}, G′_{n−4}). This and Theorem 5 imply that p = 3. Thus,

gcd(G′_{m}, G′_{n}, G′_{n−4}G′_{m+4}) = 3^{t} for some t ≥ 1.  (15)

Therefore, 3 | G′_{m} and 3 | G′_{n}. This and Theorem 7 imply that gcd(G′_{m}, G′_{m+4}) = 3 and gcd(G′_{n}, G′_{n−4}) = 3. Thus, 3 | gcd(G′_{n−4}, G′_{m+4}, G′_{m}G′_{n}). In particular, we have that 3 ≤ gcd(G′_{n−4}, G′_{m+4}, G′_{m}G′_{n}). This, (14) and (15) imply that

gcd(G′_{m}, G′_{n}, G′_{n−4}G′_{m+4}) = 3^{t} for some t ≥ 2.

Thus, G′_{m} ≡ 0 (mod 9) and G′_{n} ≡ 0 (mod 9). This proves necessity of part (1).

The proof of part (2) is analogous to the proof of part (1). Indeed, in the proof of part (1) we need to interchange the roles of a_{i} and b_{i} for i = 1, 2, 3, instead of m use m + 4, instead of n use n − 4, and also use Theorem 7. This completes the proof.

Theorem 12. Let d = gcd(a, b) and a′ = a/d, b′ = b/d. If a_{1}, a_{2}, a_{3} and b_{1}, b_{2}, b_{3} are the vertices of the star of David of length three where (m, n) are the diagonal coordinates of a_{2}, then

gcd(G′_{m+i}, G′_{n−i}, L_{2}^{2}) ≠ L_{2}^{2} for i = 0, 4 if and only if gcd(a_{1}, a_{2}, a_{3}) = gcd(b_{1}, b_{2}, b_{3}).

Proof. It is a straightforward application of Theorem 11.

5 Open Questions and a Conjecture

Theorem 9 shows that any star of David of length two has the GCD property. Theorem 12 proves that the star of David of length three has the GCD property provided that the integers a, b, m and n satisfy some L_{2}^{2}−divisibility conditions. It is natural to ask the following questions.

Open Question 1. What conditions should we impose on a, b, m and n so that the star of David of length l ≥ 2 satisfies the GCD property?

Open Question 2. If a star of David of length l ≥ 2 satisfies the GCD property, then what is the common value of gcd(a_{1}, a_{2}, a_{3}) and gcd(b_{1}, b_{2}, b_{3})?

Theorem 9 answers open questions 1 and 2 for l = 2. Theorem 12 answers open question 1 for l = 3. We propose the following conjecture to answer open question 1 for l ≥ 4.

Conjecture 13. Let d = gcd(a, b) and a′ = a/d, b′ = b/d. If a_{1}, a_{2}, a_{3} and b_{1}, b_{2}, b_{3} are the vertices of the star of David of length l where (m, n) are the diagonal coordinates of a_{2}, then

gcd(G′_{m+i}, G′_{n−i}, Q) ≠ Q for i = 0, …, 2(l − 1) if and only if gcd(a_{1}, a_{2}, a_{3}) = gcd(b_{1}, b_{2}, b_{3}),

where Q depends only on l.

l Q Relationship between Q

and Lucas number

3 3^{2}  L_{2}^{2}
4 4^{2}  L_{3}^{2}
5 7^{2}  L_{4}^{2}
6 11^{2}  L_{5}^{2}
7 18  L_{6}
8 29^{2}  L_{7}^{2}
9 47^{2}  L_{8}^{2}
10 76^{2}  L_{9}^{2}
11 123^{2}  L_{10}^{2}
12 119^{2}  L_{11}^{2}
13 322  L_{12}

Table 5: Values of Q for some l.

Table 5 gives empirical values of Q for some l ≥ 4. Notice that the value of Q for l = 3 is given by Theorem 12. We were not able to find the values of Q for l ≥ 14. We believe that the values of Q for l = 19 and l = 25 follow the same pattern as l = 7 and l = 13. These numerical results, for l ≥ 4 were found using Mathematica^{◯^{R}}.

6 Acknowledgement

The first author was partially supported by The Citadel Foundation. The third author was supported by the Small Grant from the FPDC at California University of Pennsylvania.

References

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

[2] H. W. Gould, A new greatest common divisor property of the binomial coefficients, Fibonacci Quart. 10 (1972) 579–584, 628.

[3] A. P. Hillman and V. E. Hoggatt, Jr, A proof of Gould’s Pascal hexagon conjecture, Fibonacci Quart. 10 (1972) 565–568, 598.

[4] V. E. Hoggatt Jr. and W. Hansell, The hidden hexagon squares, Fibonacci Quart. 9 (1971) 120, 133.

[5] H. Hosoya, Fibonacci triangle, Fibonacci Quart. 14 (1976) 173–178.

[6] E. Korntved, Extensions to the GCD star of David theorem, Fibonacci Quart. 10 (1994) 160–166.

[7] T. Koshy, Fibonacci and Lucas numbers with applications, John Wiley, New York, 2001.

[8] C. T. Long and S. Ando, Another generalization of Gould’s star of David theorem, Fibonacci Quart. 30 (1992) 251–255.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 20D60. Keywords: Hosoya triangle, generalized Fibonacci numbers, star of David, GCD properties, triangular arrangements.

(Concerned with sequences \underline{A000032} and \underline{A000045}.)

Received August 22 2013; revised versions received December 11 2013; January 28 2013. Published in Journal of Integer Sequences, February 16 2014.

Return to Journal of Integer Sequences home page.