Second-order linear recurrences with identically distributed residues modulo pe

Lawrence Somer and Michal Křížek
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 30, 2024, Number 1, Pages 47–66
DOI: 10.7546/nntdm.2024.30.1.47-66
Full paper (PDF, 257 Kb)

Details

Authors and affiliations

Lawrence Somer
Department of Mathematics, Catholic University of America
Washington, D.C. 20064, United States

Michal Křížek
Institute of Mathematics, Czech Academy of Sciences
Žitná 25, CZ — 115 67 Prague 1, Czech Republic

Abstract

Let p be an odd prime and let u(a,-1) and u(a',-1) be two Lucas sequences whose discriminants have the same nonzero quadratic character modulo p and whose periods modulo p are equal. We prove that there is then an integer c such that for all d\in\mathbb Z_p, the frequency with which d appears in a full period of u(a,-1)\pmod p is the same frequency as cd appears in u(a',-1)\pmod p. Here u(a,b) satisfies the recursion relation u_{n+2}=au_{n+1}+bu_n with initial terms u_0=0 and u_1=1. Similar results are obtained for the companion Lucas sequences v(a,-1) and v(a',-1). This paper extends analogous statements for Lucas sequences of the form u(a,1)\pmod p given in a previous article. We further generalize our results by showing for a certain class of primes p that if e>1, b=\pm 1, and u(a,b) and u(a',b) are Lucas sequences with the same period modulo p, then there exists an integer c such that for all residues d\pmod{p^e}, the frequency with which d appears in u(a,b)\pmod{p^e} is the same frequency as cd appears in u(a',b)\pmod{p^e}.

Keywords

  • Lucas sequences
  • Discriminant
  • Primes
  • Second-order recurrence

2020 Mathematics Subject Classification

  • 11B39
  • 11A07
  • 11A41

References

  1. Carlip, W., & Somer, L. (1999). Bounds for frequencies of residues of regular second-order recurrences modulo pr. Number Theory in Progress, Vol. 2, (Zakopane-Koscielisko, 1997), De Gruyter, Berlin, 691–719.
  2. Carmichael, R. D. (1913). On the numerical factors of arithmetic forms αn ± βn. Annals of Mathematics, 15, 30–70.
  3. Carmichael, R. D. (1920). On sequences of integers defined by recurrence relations. The Quarterly Journal of Pure and Applied Mathematics, 48, 343–372.
  4. Carroll, D., Jacobson, E., & Somer, L. (1994). Distribution of two-term recurrence
    sequences mod pe. The Fibonacci Quarterly, 32, 260–265.
  5. Lehmer, D. H. (1930). An extended theory of Lucas’ functions. Annals of Mathematics, 31, 419–448.
  6. Lucas, E. (1878). Théorie des fonctions numériques simplement périodiques. American Journal of Mathematics, 1, 184–240, 289–321.
  7. McIntosh, R. J., & Roettger, E. L. (2007). A search for Fibonacci–Wieferich and
    Wolstenholme primes. Mathematics of Computation, 76, 2087–2094.
  8. Muller, S., (1999). On the rank of appearance of Lucas sequences. In Howard, F. T. (Ed.), Applications of Fibonacci Numbers, Vol. 8 (pp. 259–275). Kluwer Academic Publishers, Dordrecht.
  9. Niederreiter, H., Schinzel, A., & Somer, L. (1991). Maximal frequencies of elements in second-order linear recurring sequences over a finite field. Elemente der Mathematik, 46, 139–143.
  10. PrimeGrid. Welcome to PrimeGrid PRPNET: Wall–Sun–Sun Prime Search. Available online at: https://www.primegrid.com/forum_thread.php?id=9436.
  11. Somer, L. (1977). Fibonacci-like groups and periods of Fibonacci-like sequences. The Fibonacci Quarterly, 15, 35–41.
  12. Somer, L. (1980). The divisibility properties of primary Lucas recurrences with respect to primes. The Fibonacci Quarterly, 18, 316–334.
  13. Somer, L. (1982). Possible periods of primary Fibonacci-like sequences with respect to a fixed odd prime. The Fibonacci Quarterly, 20, 311–333.
  14. Somer, L. (1990). Distribution of residues of certain second-order linear recurrences modulo p. In Bergum, G. E., Philippou, A. N., & Horadam, A. F. (Eds.), Applications of Fibonacci Numbers, Vol. 3 (pp. 311–324). Kluwer Academic Publishers, Dordrecht.
  15. Somer, L. (1991). Distribution of certain second-order linear recurrences modulo p – II. The Fibonacci Quarterly, 29, 72–78.
  16. Somer, L. (1993). Periodicity properties of kth order linear recurrences with irreducible characteristic polynomial over a finite field. In Mullen, G. L., & Shiue, P. J.-S. (Eds.), Finite Fields, Coding Theory and Advances in Communications and Computing (pp. 195–207). Marcel Dekker Inc., New York.
  17. Somer, L. (1993). Upper bounds for frequencies of elements in second-order recurrences over a finite field. In Bergum, G. E., Philippou, A. N., & Horadam, A. F. (Eds.), Applications of Fibonacci Numbers, Vol. 5 (pp. 527–546). St. Andrews, 1992, Kluwer Academic Publishers, Dordrecht.
  18. Somer, L. (1996). Distribution of residues of certain second-order linear recurrences modulo p – III. In Bergum, G. E., Philippou, A. N., & Horadam, A. F. (Eds.), Applications of Fibonacci Numbers, Vol. 6 (pp. 451–471). Kluwer Academic Publishers, Dordrecht.
  19. Somer, L., & Křížek, M. (2015). Identically distributed second-order linear recurrences modulo p. The Fibonacci Quarterly, 53, 290–312.
  20. Somer, L., & Křížek, M. (2016). Identically distributed second-order linear recurrences modulo p, II. The Fibonacci Quarterly, 54, 217–234.
  21. Ward, M. (1933). The arithmetical theory of linear recurring series. Transactions of the American Mathematical Society, 35, 600–628.

Manuscript history

  • Received: 8 September 2023
  • Revised: 21 February 2024
  • Accepted: 23 February 2024
  • Online First: 27 February 2024

Copyright information

Ⓒ 2024 by the Authors.
This is an Open Access paper distributed under the terms and conditions of the Creative Commons Attribution 4.0 International License (CC BY 4.0).

Related papers

Cite this paper

Somer, L., & Křížek, M. (2024). Second-order linear recurrences with identically distributed residues modulo pe. Notes on Number Theory and Discrete Mathematics, 30(1), 47-66, DOI: 10.7546/nntdm.2024.30.1.47-66.

Comments are closed.