Linear recurrence sequences without zeros. (English) Zbl 1349.11017

There are two main results in the paper. In order to quote them we recall the following. Given a positive integer \(d\) and \(2d\) fixed integers \(a_0,\dots ,a_{d-1}\) and \(x_0,\dots ,x_{d-1}\) with nonzero \(a_0\); a linear recurrent sequence \((x_n)\) of order \(d\) is defined by these data if \[ x_{n+d}=\sum_{j=0}^{d-1}a_jx_{n+j} \] for all positive integers \(n\). Call \(char(F,t)\) the monic polynomial of degree \(d\) with coefficient \(-a_j\) in \(t^j.\) For a polynomial \(A(t)\) let \(P(A)\) be the set of all prime numbers \(p\) for which \(A(t)\) has a nonzero root in \(\mathbb{Z}/p\mathbb{Z}\).
Theorem 1. There are a prime number \(p\) and \(d\) integers \(x_0,\dots ,x_{d-1}\) such that no element of the sequence \((x_n)\) is divisible by \(p\). Moreover, \(p\) can be taken in \(P(char(F,t))\).
Theorem 2. Given any positive integer \(m\) exceeding \(1\), there are a prime number \(p\) such that \(p\equiv 1 \pmod{m}\) and \(d\) integers \(x_0,\dots ,x_{d-1}\) such that every element of the sequence \((x_n)\pmod{p}\) is not a square \(\pmod{p}\).


11B37 Recurrences
11B50 Sequences (mod \(m\))
11T06 Polynomials over finite fields
Full Text: DOI Link


[1] L. M. Adleman, A. M. Odlyzko: Irreducibility testing and factorization of polynomials. Math. Comput. 41 (1983), 699–709. · Zbl 0527.12002
[2] D. Carroll, E. Jacobson, L. Somer: Distribution of two-term recurrence sequences mod p e. Fibonacci Q. 32 (1994), 260–265. · Zbl 0809.11011
[3] A. Dubickas: Distribution of some quadratic linear recurrence sequences modulo 1. Carpathian J. Math. 30 (2014), 79–86. · Zbl 1324.11048
[4] A. Dubickas: Arithmetical properties of powers of algebraic numbers. Bull. Lond. Math. Soc. 38 (2006), 70–80. · Zbl 1164.11025
[5] A. Dubickas: On the distance from a rational power to the nearest integer. J. Number Theory 117 (2006), 222–239. · Zbl 1097.11035
[6] G. Everest, A. van der Poorten, I. Shparlinski, T. Ward: Recurrence Sequences. Mathematical Surveys and Monographs 104, American Mathematical Society, Providence, 2003. · Zbl 1033.11006
[7] H. Kaneko: Limit points of fractional parts of geometric sequences. Unif. Distrib. Theory 4 (2009), 1–37. · Zbl 1249.11066
[8] H. Kaneko: Distribution of geometric sequences modulo 1. Result. Math. 52 (2008), 91–109. · Zbl 1177.11060
[9] J. C. Lagarias, A. M. Odlyzko: Effective versions of the Chebotarev density theorem. Algebraic Number Fields: L-Functions and Galois Properties (A. Fröhlich, ed.). Proc. Symp., Durham, 1975, Academic Press, London, 1977, pp. 409–464.
[10] D. Laksov: Linear recurring sequences over finite fields. Math. Scand. 16 (1965), 181–196. · Zbl 0151.01502
[11] R. Lidl, H. Niederreiter: Introduction to Finite Fields and Their Applications. Cambridge University Press, Cambridge, 1994. · Zbl 0820.11072
[12] J. Neukirch: Algebraic Number Theory. Grundlehren der Mathematischen Wissenschaften 322, Springer, Berlin, 1999. · Zbl 0956.11021
[13] H. Niederreiter, A. Schinzel, L. Somer: Maximal frequencies of elements in second-order linear recurring sequences over a finite field. Elem. Math. 46 (1991), 139–143. · Zbl 0747.11062
[14] P. Ribenboim, G. Walsh: The ABC conjecture and the powerful part of terms in binary recurring sequences. J. Number Theory 74 (1999), 134–147. · Zbl 0923.11033
[15] A. Schinzel: Polynomials with special regard to reducibility. Encyclopedia of Mathematics and Its Applications 77, Cambridge University Press, Cambridge, 2000.
[16] A. Schinzel: Special Lucas sequences, including the Fibonacci sequence, modulo a prime. A Tribute to Paul Erdös (A. Baker, et al., eds.). Cambridge University Press, Cambridge, 1990, pp. 349–357.
[17] L. Somer: Distribution of residues of certain second-order linear recurrences modulo p. Applications of Fibonacci Numbers, Vol. 3 (G. E. Bergum, et al., eds.). Proc. 3rd Int. Conf., Pisa, 1988, Kluwer Academic Publishers Group, Dordrecht, 1990, pp. 311–324.
[18] L. Somer: Primes having an incomplete system of residues for a class of second-order recurrences. Applications of Fibonacci Numbers, Proc. 2nd Int. Conf. (A. N. Philippou, et al., eds.). Dordrecht, 1988, pp. 113–141. · Zbl 0653.10005
[19] P. Stevenhagen, H. W. Lenstra, Jr.: Chebotarëv and his density theorem. Math. Intell. 18 (1996), 26–37. · Zbl 0885.11005
[20] J. F. Voloch: Chebyshev’s method for number fields. J. Théor. Nombres Bordx. 12 (2000), 81–85. · Zbl 1007.11069
[21] T. Zaïmi: An arithmetical property of powers of Salem numbers. J. Number Theory 120 (2006), 179–191. · Zbl 1147.11037
[22] Q.-X. Zheng, W.-F. Qi, T. Tian: On the distinctness of modular reductions of primitive sequences over \(\mathbb{Z}\)/(232 1). Des. Codes Cryptography 70 (2014), 359–368. · Zbl 1323.11013
[23] V. Zhuravleva: Diophantine approximations with Fibonacci numbers. J. Théor. Nombres Bordx. 25 (2013), 499–520. · Zbl 1283.11102
[24] V. Zhuravleva: On the two smallest Pisot numbers. Math. Notes 94 (2013), 820–823; translation from Mat. Zametki 94 (2013), 784–787. · Zbl 1284.11106
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.