Aurifeuillian factorizations and the period of the Bell numbers modulo a prime
HTML articles powered by AMS MathViewer
- by Samuel S. Wagstaff Jr. PDF
- Math. Comp. 65 (1996), 383-391 Request permission
Abstract:
We show that the minimum period modulo $p$ of the Bell exponential integers is $(p^p-1)/(p-1)$ for all primes $p<102$ and several larger $p$. Our proof of this result requires the prime factorization of these periods. For some primes $p$ the factoring is aided by an algebraic formula called an Aurifeuillian factorization. We explain how the coefficients of the factors in these formulas may be computed.References
-
H. W. Becker and D. H. Browne, Problem E461 and solution, Amer. Math. Monthly 48 (1941), 701–703.
- Richard P. Brent, On computing factors of cyclotomic polynomials, Math. Comp. 61 (1993), no. 203, 131–149. MR 1205459, DOI 10.1090/S0025-5718-1993-1205459-2 E. Cesaro, Sur une équation aux différences mêlées, Nouvelles Annales de Math. (3) 4 (1885), 36–40. A. J. C. Cunningham, Factorisation of $N=y^y\mp 1$ and $x^{xy}\mp y^{xy}$, Messenger of Math. (2) 45 (1915), 49–75.
- H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
- Jack Levine and R. E. Dalton, Minimum periods, modulo $p$, of first-order Bell exponential integers, Math. Comp. 16 (1962), 416–423. MR 148604, DOI 10.1090/S0025-5718-1962-0148604-2 E. Lucas, Théorèms d’arithmétique, Atti R. Accad. Sci. Torino 13 (1877–78), 271–284. E. Lucas, Sur la série récurrente de Fermat, Bull. Bibl. Storia Sc. Mat. e Fis. 11 (1878), 783–789.
- T. Beth, N. Cot, and I. Ingemarsson (eds.), Advances in cryptology, Lecture Notes in Computer Science, vol. 209, Springer-Verlag, Berlin, 1985. MR 825576, DOI 10.1007/3-540-39757-4
- Hans Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics, vol. 57, Birkhäuser Boston, Inc., Boston, MA, 1985. MR 897531, DOI 10.1007/978-1-4757-1089-2
- A. Schinzel, On primitive prime factors of $a^{n}-b^{n}$, Proc. Cambridge Philos. Soc. 58 (1962), 555–562. MR 143728, DOI 10.1017/S0305004100040561 J. Touchard, Propriétés arithmétiques de certains nombres recurrents, Ann. Soc. Sci. Bruxelles 53A (1933), 21–31.
- P. Erdös and T. Grünwald, On polynomials with only real roots, Ann. of Math. (2) 40 (1939), 537–548. MR 7, DOI 10.2307/1968938
Additional Information
- Samuel S. Wagstaff Jr.
- MR Author ID: 179915
- Email: ssw@cs.purdue.edu
- Received by editor(s): August 24, 1993
- Received by editor(s) in revised form: January 26, 1995
- Additional Notes: Some of the computing reported in this work was performed on a MasPar computer at Purdue University which was supported in part by NSF Infrastructure Grant CDA-9015696.
- © Copyright 1996 American Mathematical Society
- Journal: Math. Comp. 65 (1996), 383-391
- MSC (1991): Primary 11--04, 11B73; Secondary 11Y05, 12--04, 12E10, 12Y05
- DOI: https://doi.org/10.1090/S0025-5718-96-00683-7
- MathSciNet review: 1325876