HANDBOOK OF NUMBER THEORY II HANDBOOK OF NUMBER THEORY II by J.Sa´ndor 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´ofBelgradeUniversity, 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