Table Of Content

HANDBOOK OF NUMBER THEORY II by J.Sańdor Babes¸-BolyaiUniversityofCluj DepartmentofMathematicsandComputerScience Cluj-Napoca,Romania and B.Crstici formerlytheTechnicalUniversityofTimis¸oara Timis¸oaraRomania KLUWER ACADEMIC PUBLISHERS DORDRECHT/BOSTON/LONDON AC.I.P.CataloguerecordforthisbookisavailablefromtheLibraryofCongress. ISBN1-4020-2546-7(HB) ISBN1-4020-2547-5(e-book) PublishedbyKluwerAcademicPublishers, P.O.Box17,3300AADordrecht,TheNetherlands. SoldanddistributedinNorth,CentralandSouthAmerica byKluwerAcademicPublishers, 101PhilipDrive,Norwell,MA02061,U.S.A. Inallothercountries,soldanddistributed byKluwerAcademicPublishers, P.O.Box322,3300AHDordrecht,TheNetherlands. Printedonacid-freepaper AllRightsReserved (cid:1)C 2004KluwerAcademicPublishers Nopartofthisworkmaybereproduced,storedinaretrievalsystem,ortransmitted inanyformorbyanymeans,electronic,mechanical,photocopying,microfilming,recording orotherwise,withoutwrittenpermissionfromthePublisher,withtheexception ofanymaterialsuppliedspecificallyforthepurposeofbeingentered andexecutedonacomputersystem,forexclusiveusebythepurchaserofthework. PrintedintheNetherlands. Contents PREFACE 7 BASICSYMBOLS 9 BASICNOTATIONS 10 1 PERFECTNUMBERS:OLDANDNEWISSUES; PERSPECTIVES 15 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Somehistoricalfacts . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Evenperfectnumbers . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.4 Oddperfectnumbers . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.5 Perfect,multiperfectandmultiplyperfectnumbers . . . . . . . . . 32 1.6 Quasiperfect,almostperfect,andpseudoperfect numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.7 Superperfectandrelatednumbers . . . . . . . . . . . . . . . . . . 38 1.8 Pseudoperfect,weirdandharmonicnumbers . . . . . . . . . . . . . 42 1.9 Unitary,bi-unitary,infinitary-perfectandrelatednumbers . . . . . . 45 1.10 Hyperperfect,exponentiallyperfect,integer-perfect andγ-perfectnumbers . . . . . . . . . . . . . . . . . . . . . . . . 50 1.11 Multiplicativelyperfectnumbers . . . . . . . . . . . . . . . . . . . 55 1.12 Practicalnumbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 1.13 Amicablenumbers . . . . . . . . . . . . . . . . . . . . . . . . . . 60 1.14 Sociablenumbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 References 77 2 GENERALIZATIONSANDEXTENSIONSOFTHE MO¨BIUSFUNCTION 99 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 1 CONTENTS 2.2 Mo¨biusfunctionsgeneratedbyarithmeticalproducts (orconvolutions) . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 1 Mo¨biusfunctionsdefinedbyDirichletproducts . . . . . . . 106 2 UnitaryMo¨biusfunctions . . . . . . . . . . . . . . . . . . 110 3 Bi-unitaryMo¨biusfunction . . . . . . . . . . . . . . . . . 111 4 Mo¨biusfunctionsgeneratedbyregularconvolutions . . . . 112 5 K-convolutionsandMo¨biusfunctions. B convolution. . . . 114 6 ExponentialMo¨biusfunctions . . . . . . . . . . . . . . . . 117 7 l.c.m.-product(vonSterneck-Lehmer) . . . . . . . . . . . . 119 8 Golomb-GuerinconvolutionandMo¨biusfunction . . . . . . 121 9 max-product(Lehmer-Buschman) . . . . . . . . . . . . . . 122 10 InfinitaryconvolutionandMo¨biusfunction . . . . . . . . . 124 11 Mo¨biusfunctionofgeneralized(Beurling)integers . . . . . 124 12 Lucas-Carlitz(l-c)productandMo¨biusfunctions . . . . . . 125 13 Matrix-generatedconvolution . . . . . . . . . . . . . . . . 127 2.3 Mo¨biusfunctiongeneralizationsbyothernumbertheoretical considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 1 Apostol’sMo¨biusfunctionoforderk . . . . . . . . . . . . 129 2 Sastry’sMo¨biusfunction . . . . . . . . . . . . . . . . . . . 130 3 Mo¨biusfunctionsofHanumanthachariand Subrahmanyasastri . . . . . . . . . . . . . . . . . . . . . . 132 4 Cohen’sMo¨biusfunctionsandtotients . . . . . . . . . . . . 134 5 Klee’sMo¨biusfunctionandtotient . . . . . . . . . . . . . . 135 6 Mo¨biusfunctionsofSubbaraoandHarris;Tanaka; andVenkataramanandSivaramakrishnan . . . . . . . . . . 136 7 Mo¨biusfunctionsascoefficientsofthecyclotomic polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . 138 2.4 Mo¨biusfunctionsofposetsandlattices . . . . . . . . . . . . . . . . 139 1 Introduction,basicresults . . . . . . . . . . . . . . . . . . 139 2 Factorableincidencefunctions,applications . . . . . . . . . 143 3 Inversiontheoremsandapplications . . . . . . . . . . . . . 145 4 Mo¨biusfunctionsonEulerianposets . . . . . . . . . . . . . 146 5 Miscellaneousresults . . . . . . . . . . . . . . . . . . . . . 148 2.5 Mo¨biusfunctionsofarithmeticalsemigroups,freegroups, finitegroups,algebraicnumberfields,andtracemonoids . . . . . . 148 1 Mo¨biusfunctionsofarithmeticalsemigroups . . . . . . . . 148 2 FeeabeliangroupsandMo¨biusfunctions . . . . . . . . . . 151 3 Mo¨biusfunctionsoffinitegroups . . . . . . . . . . . . . . 154 2 CONTENTS 4 Mo¨biusfunctionsofalgebraicnumberand function-fields . . . . . . . . . . . . . . . . . . . . . . . . 159 5 TracemonoidsandMo¨biusfunctions . . . . . . . . . . . . 161 References 163 3 THEMANYFACETSOFEULER’STOTIENT 179 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 1 Theinfinitudeofprimes . . . . . . . . . . . . . . . . . . . 180 2 Exactformulaeforprimesintermsofϕ . . . . . . . . . . . 180 3 Infiniteseriesandproductsinvolving ϕ,Pillai’s(Cesa`ro’s)arithmeticfunctions . . . . . . . . . . 181 4 Enumerationproblemsoncongruences,directed graphs,magicsquares . . . . . . . . . . . . . . . . . . . . 183 5 Fouriercoefficientsofevenfunctions(modn) . . . . . . . . 184 6 Algebraicindependenceofarithmeticfunctions . . . . . . . 185 7 Algebraicandanalyticapplicationoftotients . . . . . . . . 186 8 ϕ-convergenceofSchoenberg . . . . . . . . . . . . . . . . 187 3.2 CongruencepropertiesofEuler’stotientandrelatedfunctions. . . . 188 1 Euler’sdivisibilitytheorem . . . . . . . . . . . . . . . . . . 188 2 Carmichael’sfunction,maximalgeneralizationof Fermat’stheorem . . . . . . . . . . . . . . . . . . . . . . . 189 3 Gauss’divisibilitytheorem . . . . . . . . . . . . . . . . . . 191 4 Minimal,normal,andaverageorderofCarmichael’s function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 5 Divisibilitypropertiesofiterationofϕ . . . . . . . . . . . . 195 6 Congruencepropertiesofϕ andrelatedfunctions . . . . . . 201 7 Euler’stotientinresidueclasses . . . . . . . . . . . . . . . 204 8 Primetotatives . . . . . . . . . . . . . . . . . . . . . . . . 206 9 Thedualofϕ,noncototients . . . . . . . . . . . . . . . . . 208 10 Eulerminimumfunction . . . . . . . . . . . . . . . . . . . 210 11 Lehmer’sconjecture,generalizationsandextensions . . . . 212 3.3 EquationsinvolvingEuler’sandrelatedtotients . . . . . . . . . . . 216 1 Equationsoftypeϕ(x +k) = ϕ(x) . . . . . . . . . . . . . 216 2 ϕ(x +k) = 2ϕ(x +k) = ϕ(x)+ϕ(k)andrelated equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 3 Equationϕ(x) = k,Carmichael’sconjecture . . . . . . . . 225 4 Equationsinvolvingϕ andotherarithmeticfunctions . . . . 230 5 Thecompositionofϕ andotherarithmeticfunctions . . . . 234 6 Perfecttotientnumbersandrelatedresults . . . . . . . . . . 240 3 CONTENTS 3.4 Thetotatives(ortotitives)ofanumber . . . . . . . . . . . . . . . . 242 1 Historicalnotes,congruences . . . . . . . . . . . . . . . . 242 2 Thedistributionoftotatives . . . . . . . . . . . . . . . . . 246 3 Addingtotatives . . . . . . . . . . . . . . . . . . . . . . . 248 4 Addingunits (mod n) . . . . . . . . . . . . . . . . . . . . 249 5 Distributionofinverses (mod n) . . . . . . . . . . . . . . 250 3.5 Cyclotomicpolynomials . . . . . . . . . . . . . . . . . . . . . . . 251 1 Introduction,irreducibilityresults . . . . . . . . . . . . . . 251 2 Divisibilityproperties . . . . . . . . . . . . . . . . . . . . 253 3 Thecoefficientsofcyclotomicpolynomials . . . . . . . . . 256 4 Miscellaneousresults . . . . . . . . . . . . . . . . . . . . . 261 3.6 Matricesanddeterminantsconnectedwithϕ . . . . . . . . . . . . . 263 1 Smith’sdeterminant . . . . . . . . . . . . . . . . . . . . . 263 2 Poset-theoreticgeneralizations . . . . . . . . . . . . . . . . 266 3 Factor-closed,gcd-closed,lcm-closedsets,and relateddeterminants . . . . . . . . . . . . . . . . . . . . . 270 4 Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . 273 3.7 GeneralizationsandextensionsofEuler’stotient . . . . . . . . . . . 275 1 Jordan,Jordan-Nagell,vonSterneck,Cohen-totients . . . . 275 2 Schemmel,Schemmel-Nagell,Lucas-totients . . . . . . . . 276 3 Ramanujan’ssum . . . . . . . . . . . . . . . . . . . . . . . 277 4 Klee’stotient . . . . . . . . . . . . . . . . . . . . . . . . . 278 5 Nagell’s,Adler’s,Stevens’,KesavaMenon’stotients . . . . 278 6 Unitary,semi-unitary,bi-unitarytotients . . . . . . . . . . . 281 7 Alladi’stotient . . . . . . . . . . . . . . . . . . . . . . . . 282 8 Legendre’stotient. . . . . . . . . . . . . . . . . . . . . . . 283 9 Eulertotientsofmeetsemilatticesandfinitefields . . . . . 285 10 Nonunitary,infinitary,exponential-totients . . . . . . . . . 287 11 Thacker’s,Leudesdorf’s,Lehmer’s,Golubev’stotients. Squaretotient,core-reducedtotient,M-voidtotient, additivetotient . . . . . . . . . . . . . . . . . . . . . . . . 289 12 Eulertotientsofarithmeticalsemigroups,finitegroups, algebraicnumberfields,semigroups,finitecommutative rings,finiteDedekinddomains . . . . . . . . . . . . . . . . 292 References 295 4 SPECIALARITHMETICFUNCTIONSCONNECTEDWITH THEDIVISORS,ORWITHTHEDIGITSOFANUMBER 329 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 4 CONTENTS 4.2 Specialarithmeticfunctionsconnectedwiththedivisors ofanumber . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 1 Maximumandminimumexponents . . . . . . . . . . . . . 330 2 Theproductofexponents. . . . . . . . . . . . . . . . . . . 332 3 Arithmeticfunctionsconnectedwiththeprimepower factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 4 Otherfunctions;thederivedsequenceofanumber . . . . . 336 5 Theconsecutiveprimedivisorsofanumber . . . . . . . . . 337 6 Theconsecutivedivisorsofaninteger . . . . . . . . . . . . 342 7 Functionallimittheoremsfortheconsecutivedivisors . . . 343 8 Miscellaneousarithmeticfunctionsconnectedwith divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 9 Arithmeticfunctionsofconsecutivedivisors . . . . . . . . . 349 10 Hooley’s(cid:3)function . . . . . . . . . . . . . . . . . . . . . 360 11 ExtensionsoftheErdo¨sconjecture(theorem) . . . . . . . . 363 12 Thedivisorsinresidueclassesandinintervals . . . . . . . 363 13 Divisordensityanddistribution (mod 1)ondivisors . . . . 366 14 Thefractalstructureofdivisors . . . . . . . . . . . . . . . 367 15 Thedivisorgraphs . . . . . . . . . . . . . . . . . . . . . . 369 4.3 Arithmeticfunctionsassociatedtothedigitsofanumber . . . . . . 371 1 Theaverageorderofthesum-of-digitsfunction . . . . . . . 371 2 Boundsonthesum-of-digitsfunction . . . . . . . . . . . . 376 3 Thesumofdigitsofprimes . . . . . . . . . . . . . . . . . 379 4 Nivennumbers . . . . . . . . . . . . . . . . . . . . . . . . 381 5 Smithnumbers . . . . . . . . . . . . . . . . . . . . . . . . 383 6 Selfnumbers . . . . . . . . . . . . . . . . . . . . . . . . . 384 7 Thesum-of-digitsfunctioninresidueclasses . . . . . . . . 387 8 Thue-MorseandRudin-Shapirosequences . . . . . . . . . 390 9 q-additiveandq-multiplicativefunctions . . . . . . . . . . 401 10 Uniform-andwell-distributionsofαs (n) . . . . . . . . . 410 q 11 TheG-arydigitalexpansionofanumber . . . . . . . . . . 414 12 Thesum-of-digitsfunctionfornegativeintegerbases . . . . 417 13 Thesum-of-digitsfunctioninalgebraicnumberfields . . . . 418 14 Thesymmetricsigneddigitalexpansion . . . . . . . . . . . 421 15 Infinitesumsandproductsinvolvingthesum-of-digits function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 16 Miscellaneousresultsondigitalexpansions . . . . . . . . . 427 References 433 5 CONTENTS 5 STIRLING,BELL,BERNOULLI,EULERAND EULERIANNUMBERS 459 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459 5.2 StirlingandBellnumbers . . . . . . . . . . . . . . . . . . . . . . . 459 1 Stirlingnumbersofbothkinds,Lahnumbers . . . . . . . . 459 2 IdentitiesforStirlingnumbers . . . . . . . . . . . . . . . . 464 3 GeneralizedStirlingnumbers . . . . . . . . . . . . . . . . 469 4 CongruencesforStirlingandBellnumbers . . . . . . . . . 488 5 Diophantineresults . . . . . . . . . . . . . . . . . . . . . . 507 6 Inequalitiesandestimates . . . . . . . . . . . . . . . . . . 508 5.3 BernoulliandEulernumbers . . . . . . . . . . . . . . . . . . . . . 525 1 Definitions,basicpropertiesofBernoullinumbers andpolynomials . . . . . . . . . . . . . . . . . . . . . . . 525 2 Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . 534 3 CongruencesforBernoullinumbersandpolynomials. Euleriannumbersandpolynomials . . . . . . . . . . . . . . 539 4 Estimatesandinequalities . . . . . . . . . . . . . . . . . . 574 References 585 Index 619 6 Preface Theaimofthisbookistosystematizeandsurveyinaneasilyaccessiblemanner themostimportantresultsfromsomepartsofNumberTheory,whichareconnected withmanyotherfieldsofMathematicsorScience.Eachchaptercanbeviewedasan encyclopediaoftheconsideredfield,withmanyfacetsandinterconnectionswithvir- tuallyalmostallmajortopicsasDiscretemathematics,Combinatorialtheory,Numer- ical analysis, Finite difference calculus, Probability theory; and such classical fields of mathematics as Algebra, Geometry, and Mathematical analysis. Some aspects of Chapter1and3onPerfectnumbersandEuler’stotient,havebeenconsideredalsoin our former volume ”Handbook of Number Theory” (Kluwer Academic Publishers, 1995),incooperationwiththelateProfessorD.S.MitrinovicófBelgradeUniversity, aswellasProfessorB.Crstici,formerlyofTimis¸oaraTechnicalUniversity.However, therewereincludedmainlyestimatesandinequalities,whichareindeedveryuseful, but many important relations (e.g. congruences) were left out, giving a panoramic viewofmanyotherpartsofNumberTheory. Thisvolumeaimsalsotocomplementtheseissues,andalsotobringtotheatten- tion of the readers (specialists or not) the hidden beauty of many theories outside a givenfieldofinterest. Thisbookfocusestoo,astheformervolume,onsomeimportantarithmeticfunc- tions of Number Theory and Discrete mathematics, such as Euler’s totient ϕ(n) and its many generalizations; the sum of divisors function σ(n) with the many old and new issues on Perfect numbers; the Mo¨bius function, along with its generalizations and extensions, in connection with many applications; the arithmetic functions re- latedtothedivisors,consecutivedivisors,orthedigitsofanumber.Thelastchapter showsperhapsmoststrikinglythecross-fertilizationofNumbertheorywithCombi- natorics,Numericalmathematics,orProbabilitytheory. The style of presentation of the material differs from that of our former volume, since we have opted here for a more flexible, conversational, survey-type method. Eachchapterisconcludedwithadetailedandup-to-datelistofReferences,whileat theendofthebookonecanfindanextensiveSubjectindex. 7 PREFACE We have used a wealth of literature, consisting of books, monographs, journals, separates, reviews from Mathematical Reviews and from Zentralblatt fu¨r Mathe- matik, etc. This volume was not possible to elaborate without the kind support of many people. The author is indebted to scientists all over the world, for providing him along the years reprints of their papers, books, letters, or personal communi- cations. Special thanks are due to Professors A. Adelberg, G. Andrews, T. Agoh, R.Askey,H.Alzer,J.-P.Allouche,K.Atanassov,E.Bach,A.Blass,W.Borho,P.B. Borwein,D.W.Boyd,D.Berend,R.G.Buschman,A.Balog,A.Baker,B.C.Berndt, R. de la Brete`che, B. C. Carlson, C. Cooper, G. L. Cohen, M. Deaconescu, R. Dus- saud, M. Drmota, J. De´sarmeńien, K. Dilcher, P. Erdo¨s, P. D. T. A. Elliott, M. Eie, S. Finch, K. Ford, J. B. Friedlander, J. Fehe´r, A. A. Gioia, A. Grytczuk, K. Gyo¨ry, J.Galambos,J.M.DeKoninck,P.J.Grabner,H.W.Gould,E.-U.Gekeler,P.Hagis, Jr., D. R. Heath-Brown, H. Harborth, P. Haukkanen, A. Hildebrand, A. Hoit, F. T. Howard,L.Habsieger,J.J.Holt,A.Ivic´,H.Iwata,K.-H.Indlekofer,F.Halter-Koch, H.-J.Kanold,M.Kishore,I.Ka´tai,P.A.Kemp,E.Kra¨tzel,T.Kim,G.O.H.Katona, P. Leroux, A. Laforgia, A. T. Lundell, F. Luca, D. H. Lehmer, A. Makowski, M. R. Murthy,V.K.Murthy,P.Moree,H.Maier,E.Manstavicˇius,N.S.Mendelsohn,J.-L. Nicolas,E.Neuman,W.G.Novak,H.Niederhausen,C.Pomerance,Sˇ.Porubsky´,L. Panaitopol,J.E.Pecˇaric´,Zs.Pa´les,A.Peretti,H.J.J.teRiele,B.Rizzi,D.Redmond, N. Robbins, P. Ribenboim, I. Z. Ruzsa, H. N. Shapiro, M. V. Subbarao, A. Sa´rko¨zy, A.Schinzel,R.Sivaramakrishnan,J.Surańyi,T.Sˇala´t,J.O.Shallit,K.B.Stolarsky, B. E. Sagan, I. Sh. Slavutskii, F. Schipp, V. E. S. Szabo´, L. To´th, G. Tenenbaum, R. F. Tichy, J. M. Thuswaldner, Gh. Toader, R. Tijdeman, N. M. Temme, H. Tsumura, R.Wiegandt,S.S.Wagstaff,Jr.,Ch.Wall,B.Wegner,M.Wo´jtowicz. The author wishes to express his gratitude also to a number of organizations whomhereceivedadviceandsupportinthepreparationofthismaterial.Thesearethe Mathematics Department of the Babes¸-Bolyai University, the Alfred Reńyi Institute of Mathematics (Budapest), the Domus Hungarica Foundation of Hungary, and the Sapientia Foundation of Cluj, Romania. The gratefulness of the author is addressed tothestaffofKluwerAcademicPublishers,especiallytoMr.MarliesVlot,Ms.Lynn BrandonandMs.LiesbethMolfortheirsupportwhiletypesettingthemanuscript. The camera-ready manuscript for the present book was prepared by Mrs.GeorgetaBonda(Cluj)towhomtheauthorexpresseshisgratitude. Theauthor 8