Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Aurifeuillian factorizations and the period of the Bell numbers modulo a prime


Author: Samuel S. Wagstaff Jr.
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
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1 H. W. Becker and D. H. Browne, Problem E461 and solution, Amer. Math. Monthly 48 (1941), 701--703.
  • 2 Richard P. Brent, On computing factors of cyclotomic polynomials, Math. Comp. 61 (1993), 131--149, MR 93m:11131.
  • 3 E. Cesaro, Sur une équation aux différences mêlées, Nouvelles Annales de Math. (3) 4 (1885), 36--40.
  • 4 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.
  • 5 H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649--673, MR 89g:11125.
  • 6 Jack Levine and R. E. Dalton, Minimum periods, modulo $p$, of first-order Bell exponential integers, Math. Comp. 16 (1962), 416--423, MR 26:6111.
  • 7 E. Lucas, Théorèms d'arithmétique, Atti R. Accad. Sci. Torino 13 (1877--78), 271--284.
  • 8 ------, Sur la série récurrente de Fermat, Bull. Bibl. Storia Sc. Mat. e Fis. 11 (1878), 783--789.
  • 9 Carl Pomerance, The quadratic sieve factoring algorithm, Advances in Cryptology, Proceedings of EUROCRYPT 84 (T. Beth, N. Cot, and I. Ingemarsson, eds.), Springer-Verlag Lecture Notes in Comput. Sci., vol. 209, 1985, pp. (169--182), MR 86m:94003.
  • 10 Hans Riesel, Prime numbers and computer methods for factorization, Birkhäuser, Boston, 1985, MR 88k:11002.
  • 11 A. Schinzel, On the primitive prime factors of $a^n-b^n$, Proc. Cambridge Philos. Soc. 58 (1962), 555--562, MR 26:1280.
  • 12 J. Touchard, Propriétés arithmétiques de certains nombres recurrents, Ann. Soc. Sci. Bruxelles 53A (1933), 21--31.
  • 13 G. T. Williams, Numbers generated by the function $e^{e^x-1}$, Amer. Math. Monthly 52 (1945), 323--327, MR 7:47e.

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11--04, 11B73, 11Y05, 12--04, 12E10, 12Y05

Retrieve articles in all journals with MSC (1991): 11--04, 11B73, 11Y05, 12--04, 12E10, 12Y05


Additional Information

Samuel S. Wagstaff Jr.
Email: ssw@cs.purdue.edu

DOI: https://doi.org/10.1090/S0025-5718-96-00683-7
Keywords: Bell numbers, period modulo $p$, integer factorization, Lucas' identities, Aurifeuillian factorization
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.
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society