# zbMATH — the first resource for mathematics

The g.c.d. in Lucas sequences and Lehmer number sequences. (English) Zbl 0732.11008
Two second-order linear recurring sequences $$\{U_ k\}$$, $$\{V_ k\}$$ $$(k=0,1,...)$$ are defined as follows $U_ 0=0,\quad U_ 1=1,\quad U_{n+2}=PU_{n+1}-QU_ n,\quad V_ 0=2,\quad V_ 1=P,\quad V_{n+2}=PV_{n+1}-QV_ n\quad (n=0,1,...),$ where P and Q are relatively prime integers. The characteristic polynomial of both sequences is $$f(x)=x^ 2-Px+Q$$ and f(x) is assumed to have different roots. (If $$P=1$$ and $$Q=-1$$ we get the Fibonacci and Lucas numbers.) The following theorem is stated: Let $$m=2^ am'$$, $$n=2^ bn'$$, $$m'$$ and $$n'odd$$, a and b non-negative integers, and let $$d=\gcd (m,n)$$. Then (i) $$\gcd (U_ m,U_ n)=U_ d$$, (ii) $$\gcd (V_ m,V_ n)=V_ d$$ if $$a=b$$, and in opposite case $$=1$$ or 2, (iii) $$\gcd (U_ m,V_ n)=V_ d$$ if $$a=b$$, and in opposite case $$=1$$ or 2. These results go back to Lucas (1878), the part (i), for $$a=b$$ the part (ii) and for $$m=n$$ the part (iii). Finally analogous results are stated for Lehmer and “associated” Lehmer numbers.
Reviewer: L.Skula (Brno)

##### MSC:
 11B39 Fibonacci and Lucas numbers and polynomials and generalizations 11B37 Recurrences 11A05 Multiplicative structure; Euclidean algorithm; greatest common divisors