Distribution of residues of certain second-order linear recurrences modulo p. (English) Zbl 0722.11008

Applications of Fibonacci numbers. Vol. 3, Proc. 3rd Int. Conf., Pisa/Italy 1988, 311-324 (1990).
[For the entire collection see Zbl 0699.00017.]
Let u(a,1) be a sequence of integers defined by \(u_{n+2}=au_{n+1}+u_ n\) with \(u_ 0=0\), \(u_ 1=1\). It is well- known that this sequence is purely periodic modulo p for any odd prime p. Denote the length of the minimal period of u(a,1) modulo p by \(\omega\) (p). The restricted period of the sequence modulo p, denoted by \(\alpha\) (p), is the least positive t such that \(u_{n+t}\equiv su_ n(mod p)\) for all non-negative n and some nonzero residue s. Denote by N(p) the number of distinct residues which appear in u(a,1) modulo p and by A(d) the number of times the residue d appears in a period modulo p. The author presents various results concerning the numbers N(p) and A(d). Some typical results are the following ones. If \(\omega (p)/\alpha (p)=2\) and \(p\nmid a\), then \(A(d)=A(-d)\), \(A(d)=0\), 1, 2, 3, or 4 and \(\alpha (p)/2+1\leq N(p)\leq \alpha (p)+7\). If \(\alpha (p)=p+1\) is also satisfied, then \(N(p)=(3p+c)/4\), where \(c=3\) or 7 depending on the form of p.
Reviewer: P.Kiss (Eger)


11B37 Recurrences
11B39 Fibonacci and Lucas numbers and polynomials and generalizations


Zbl 0699.00017