Aurifeuillian factorization

Granville, Andrew; Pleasants, Peter

doi:10.1090/S0025-5718-05-01766-7

Aurifeuillian factorization
HTML articles powered by AMS MathViewer

by Andrew Granville and Peter Pleasants PDF

Math. Comp. 75 (2006), 497-508 Request permission

Abstract:

The Cunningham project seeks to factor numbers of the form $b^{n}\pm 1$ with $b=2,3,\dots$ small. One of the most useful techniques is Aurifeuillian Factorization whereby such a number is partially factored by replacing $b^{n}$ by a polynomial in such a way that polynomial factorization is possible. For example, by substituting $y=2^{k}$ into the polynomial factorization $(2y^{2})^{2}+1=(2y^{2}-2y+1)(2y^{2}+2y+1)$ we can partially factor $2^{4k+2}+1$. In 1962 Schinzel gave a list of such identities that have proved useful in the Cunningham project; we believe that Schinzel identified all numbers that can be factored by such identities and we prove this if one accepts our definition of what “such an identity” is. We then develop our theme to similarly factor $f(b^{n})$ for any given polynomial $f$, using deep results of Faltings from algebraic geometry and Fried from the classification of finite simple groups.

References

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
John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^n \pm 1$, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. $b=2,3,5,6,7,10,11,12$ up to high powers. MR 996414, DOI 10.1090/conm/022
Henri Darmon and Andrew Granville, On the equations $z^m=F(x,y)$ and $Ax^p+By^q=Cz^r$, Bull. London Math. Soc. 27 (1995), no. 6, 513–543. MR 1348707, DOI 10.1112/blms/27.6.513
G. Faltings, Endlichkeitssätze für abelsche Varietäten über Zahlkörpern, Invent. Math. 73 (1983), no. 3, 349–366 (German). MR 718935, DOI 10.1007/BF01388432
Gerd Faltings, Diophantine approximation on abelian varieties, Ann. of Math. (2) 133 (1991), no. 3, 549–576. MR 1109353, DOI 10.2307/2944319
M. Fried, Applications of the classification of simple groups to monodromy, Part II: Davenport and Hilbert-Siegel problems (to appear).
Carl Friedrich Gauss, Disquisitiones arithmeticae, Yale University Press, New Haven, Conn.-London, 1966. Translated into English by Arthur A. Clarke, S. J. MR 0197380
S. Hahn, A remark on Aurifeuilian factorizations, Math. Japon. 39 (1994), no. 3, 501–502. MR 1278865
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èmes d’arithmétique, Atti. Roy. Acad. Sci. Torino 13 (1878), 271–284.
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
A. Schinzel and R. Tijdeman, On the equation $y^{m}=P(x)$, Acta Arith. 31 (1976), no. 2, 199–204. MR 422150, DOI 10.4064/aa-31-2-199-204
Carl Ludwig Siegel, Gesammelte Abhandlungen. Bände I, II, III, Springer-Verlag, Berlin-New York, 1966 (German). Herausgegeben von K. Chandrasekharan und H. Maass. MR 0197270
Peter Stevenhagen, On Aurifeuillian factorizations, Nederl. Akad. Wetensch. Indag. Math. 49 (1987), no. 4, 451–468. MR 922449, DOI 10.1016/1385-7258(87)90009-6
Q. Sun and Shao Fang Hong, Aurifeuillian factorizations of $q^q\pm 1\ (q=p^n)$, Gaoxiao Yingyong Shuxue Xuebao Ser. A 13 (1998), no. 3, 342–348 (Chinese, with English and Chinese summaries). MR 1646160
Qi Sun, Debin Ren, Shaofang Hong, Pingzhi Yuan, and Qing Han, A new class of Aurifeuillian factorizations of $M^n\pm 1$, Sci. Math. 2 (1999), no. 3, 353–360. MR 1718279
Samuel S. Wagstaff Jr., Aurifeuillian factorizations and the period of the Bell numbers modulo a prime, Math. Comp. 65 (1996), no. 213, 383–391. MR 1325876, DOI 10.1090/S0025-5718-96-00683-7