## Linear recurrence sequences satisfying congruence conditions

HTML articles powered by AMS MathViewer

- by Gregory T. Minton PDF
- Proc. Amer. Math. Soc.
**142**(2014), 2337-2352 Request permission

## Abstract:

It is well-known that there exist integer linear recurrence sequences $\{x_n\}$ such that $x_p \equiv x_1$ (mod $p$) for all primes $p$. It is less well-known, but still classical, that there exist such sequences satisfying the stronger condition $x_{p^n} \equiv x_{p^{n-1}}$ (mod $p^n$) for all primes $p$ and $n \ge 1$, or even $m \mid \sum _{d \mid m} \mu (m/d) x_d$ for all $m \ge 1$. These congruence conditions generalize Fermat’s little theorem, Euler’s theorem, and Gauss’s congruence, respectively. In this paper we classify sequences of these three types. Our classification for the first type is in terms of linear dependencies of the characteristic zeros; for the second, it involves recurrence sequences vanishing on arithmetic progressions; and for the last type we give an explicit classification in terms of traces of powers.## References

- William Adams and Daniel Shanks,
*Strong primality tests that are not sufficient*, Math. Comp.**39**(1982), no. 159, 255–300. MR**658231**, DOI 10.1090/S0025-5718-1982-0658231-9 - B. Amend,
*FoxTrot comic strip*, 2005, http://www.gocomics.com/foxtrot/2005/10/11. - Neil Berry, Artūras Dubickas, Noam D. Elkies, Bjorn Poonen, and Chris Smyth,
*The conjugate dimension of algebraic numbers*, Q. J. Math.**55**(2004), no. 3, 237–252. MR**2082091**, DOI 10.1093/qjmath/55.3.237 - A. Dold,
*Fixed point indices of iterated maps*, Invent. Math.**74**(1983), no. 3, 419–435. MR**724012**, DOI 10.1007/BF01394243 - E. Escott,
*Reply to query 1484*, L’Intermédiaire des Math.**8**(1901), 63–64. - —,
*Solution to problem 151*, Amer. Math. Monthly**15**(1908), no. 10, 187. - Mihaly Bencze, Dan Saracino, Allen Stenger, S. Amghibech, J. Anglesio, R. Bauer, A. Siegel, D. M. Bloom, G. L. Body, D. Callan, R. J. Chapman, K. Ford, S. M. Gagola, N. Gauthier, W. V. Grounds, T. Hagedorn, R. T. Koether, N. Komanda, R. N. Krishnan, K.-W. Lau, J. H. Lindsey II, L. E. Mattics, C. A. Minh, H. N. Ozsoylev, C. Y. Yildirim, P. G. Poonacha, N. R. Sanjeev, C. Popescu, J. Robertson, H.-J. Sieffert, J. O. Shallit, N C. Singer, A. Stadler, D. C. Terr, T. V. Triff, T. Trimble, P. Trojovsky, Anchorage Math Solutions Group, GCHQ Problems Group, and NSA Problems Group,
*Problems and Solutions: Solutions: A Recurrence Generating Multiples of Primes: 10655*, Amer. Math. Monthly**107**(2000), no. 3, 281–282. MR**1543639**, DOI 10.2307/2589334 - Graham Everest, Alf van der Poorten, Igor Shparlinski, and Thomas Ward,
*Recurrence sequences*, Mathematical Surveys and Monographs, vol. 104, American Mathematical Society, Providence, RI, 2003. MR**1990179**, DOI 10.1090/surv/104 - Irving Gerst and John Brillhart,
*On the prime divisors of polynomials*, Amer. Math. Monthly**78**(1971), 250–266. MR**279071**, DOI 10.2307/2317521 - Frank S. Gillespie,
*A generalization of Fermat’s little theorem*, Fibonacci Quart.**27**(1989), no. 2, 109–115. MR**995558** - Kurt Girstmair,
*Linear dependence of zeros of polynomials and construction of primitive elements*, Manuscripta Math.**39**(1982), no. 1, 81–97. MR**672402**, DOI 10.1007/BF01312446 - Kurt Girstmair,
*Linear relations between roots of polynomials*, Acta Arith.**89**(1999), no. 1, 53–96. MR**1692195**, DOI 10.4064/aa-89-1-53-96 - Jon Grantham,
*There are infinitely many Perrin pseudoprimes*, J. Number Theory**130**(2010), no. 5, 1117–1128. MR**2607304**, DOI 10.1016/j.jnt.2009.11.008 - H. W. Lenstra Jr. and P. Stevenhagen,
*Primes of degree one and algebraic cases of Čebotarev’s theorem*, Enseign. Math. (2)**37**(1991), no. 1-2, 17–30. MR**1115741** - P. Stevenhagen and H. W. Lenstra Jr.,
*Chebotarëv and his density theorem*, Math. Intelligencer**18**(1996), no. 2, 26–37. MR**1395088**, DOI 10.1007/BF03027290 - G. Minton,
*Three approaches to a sequence problem*, Math. Mag.**84**(2011), no. 1, 33–37. -
*The On-Line Encyclopedia of Integer Sequences*, http://oeis.org, 2012. - Yash Puri and Thomas Ward,
*A dynamical property unique to the Lucas sequence*, Fibonacci Quart.**39**(2001), no. 5, 398–402. MR**1866354** - A. Schinzel,
*Reducibility of lacunary polynomials. VIII*, Acta Arith.**50**(1988), no. 1, 91–106. MR**945276**, DOI 10.4064/aa-50-1-91-106 - C. J. Smyth,
*A coloring proof of a generalisation of Fermat’s little theorem*, Amer. Math. Monthly**93**(1986), no. 6, 469–471. MR**843194**, DOI 10.2307/2323475 - R. Tudoran,
*A well-known sequence*, College Math. J.**31**(2000), no. 3, 223–224. - A. V. Zarelua,
*On matrix analogues of Fermat’s little theorem*, Mat. Zametki**79**(2006), no. 6, 838–853 (Russian, with Russian summary); English transl., Math. Notes**79**(2006), no. 5-6, 783–796. MR**2261239**, DOI 10.1007/s11006-006-0090-y - A. V. Zarelua,
*On congruences for the traces of powers of some matrices*, Tr. Mat. Inst. Steklova**263**(2008), no. Geometriya, Topologiya i Matematicheskaya Fizika. I, 85–105 (Russian, with Russian summary); English transl., Proc. Steklov Inst. Math.**263**(2008), no. 1, 78–98. MR**2599373**, DOI 10.1134/S008154380804007X

## Additional Information

**Gregory T. Minton**- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139
- Address at time of publication: Microsoft Research New England, One Memorial Drive, Cambridge, Massachusetts 02142
- Email: gminton@alum.mit.edu
- Received by editor(s): August 2, 2012
- Published electronically: April 4, 2014
- Additional Notes: The author was supported by a Fannie and John Hertz Foundation Fellowship and a National Science Foundation Graduate Research Fellowship
- Communicated by: Ken Ono
- © Copyright 2014
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc.
**142**(2014), 2337-2352 - MSC (2010): Primary 11B50, 11R45
- DOI: https://doi.org/10.1090/S0002-9939-2014-12168-X
- MathSciNet review: 3195758