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)

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