## 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)

### MSC:

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

### Keywords:

linear recurrences modulo p; period modulo p

Zbl 0699.00017