; TeX output 2005.05.15:1551 nE&color push Blackhtml:color push gray 0 color pop html: color pop3ڍ֠|&html: html:.MTvkcolor push Black color popZVg5PSfile=logo129.eps llx=0 lly=0 urx=99 ury=16 rwi=2880Bs獍
color push Black color popm N q cmbx12On
DivisibilitZyofNarayanaNumb ersby :9 A}Primes.s獒 *\XQ ff cmr12Mikl9os/Bona ˕Department/ofMathematics University/ofFlorida Gainesville,/FL32611 dUSA (html:color push cmyk 0 1 0 0߆T ff cmtt12bona@math.ufl.edu html: color pop Bruce/E.Sagan ˕Department/ofMathematics [ZMichigan/StateUniversity East/Lansing,MI48824-1027 dUSA 0)html:color push cmyk 0 1 0 0sagan@math.msu.edu html: color pop)
č vcolor push Black color pop r"V
3
cmbx10AbstractMƍlcolor push Black color pop-̻K`y
3
cmr10UsingnKummer'stheorem,:w!egiveanecessaryandsucientconditionforaNarayana
_n!umbMer html:N G cmbx121(Thezmaintheoremb#XQ cmr12Let%
msbm10Ndenotethenonnegativreintegersandletg cmmi12kg;n!",
cmsy102N.]The+@ cmti12Narffayana+numbers[html:color push cmyk 0 1 0 010 html: color pop, A001263]canbSedenedasfo ^N@(n;kg)UR=ōL1[ z
nAqu
cmex10ōnYyԘk"q%mzqō8/=nYy.BkŹ+1I1qpwhereI0>k[color push cmyk 0 1 0 06 html: color pop,Article495]andwerelaterrediscoveredbyNarayana[html:color push cmyk 0 1 0 07 html: color pop].Theyareclosely color push Black 1 color pop *c.color push Blackhtml:color push gray 0 color pop html: color pop[(ֹrelatedtotheCatalan35numbffers腹[html:color push cmyk 0 1 0 010 html: color pop,A000108]!-荒 TC2 cmmi8n=ōF1[ z \]
n+1!qō)m2nYy,kn6q!-ֹand infactP\k=N@(n;kg)UR=CnP.%The NararyananumbSerscanbearrangedinatriangulararrary withCKN@(n;kg)inrorwnandcolumnkhsothattherowsumsaretheCatalannumbSers.LikethenrumbSersLCnP,+thenrumbersLN@(n;kg)harveLmanycombinatorialinterpretations;=see,+forexample,thearticleofSulankre[html:color push cmyk 0 1 0 011 html: color pop].+ThemainresultofthisnoteisacrharacterizationofwhenN@(n;kg)isdivisiblebyagivenprime5-p. oTVostateit,wreneedsomenotation.Letp](n)=(nidڹ)5-denotethesequenceofdigitsLofninbasepsothatn=PZinidp2i. _SimilarlyLwredenep](kg)=(kidڹ).IfLwreareconsideringLjkoURnthenitwillbSeconrvenientLjtoextendtherangeofdenitionof(kidڹ)sothatbSoth0sequencesharve0thesamelengthbrysettingki1=A0ifp2i>Akg.
Theorffder{3ofnmoSdulopֹisUthelargestpSorwerUofpdividingnandwillbedenoted!p](n).Asusual,&@kgjnmeansthatkֹdividesn.+Kummer'stheorem[html:color push cmyk 0 1 0 05 html: color pop]givresausefulwayofndingtheorderofbinomialcoSecients.FVorexample,KnruthandWilf[html:color push cmyk 0 1 0 04 html: color pop]usedittondthehighestpSowerofaprimewhichdividesageneralizedbinomialcoSecienrt.8 html: html:Ocolor push Black,N cmbx12Theorem 1.1(Kummer) color pop "Lffetpbeprimeandletp](n)UR=(nidڹ),p(kg)=(kidڹ).PThen!pG ܍
G_n v~
koGisthenumbfferofcarriesinperformingtheadditionp](kg)@+p(n kg).;Equivalently,ȷitisthelQnumbfferofindicesisuchthateitherki#>ni+orthereexistsanindexjk<iwithkj%>njand35kjv|{Y cmr8+1ع=URnjv+1B;:::ʜ;ki,=nid. * *?e+ʹNorweverythingisinplacetostateandproveourprincipaltheorem.8 html: html:color push BlackTheorem 1.2 color popALffetypbeprime.5A2lsoletp](n)A=(nidڹ),ʹp(kg)=(kidڹ)yand!z=A!p(n).5ThenpUR-N@(n;kg)35ifandonlyifoneofthetwofol lowingcffonditionshold:֟html: html:scolor push Blackfa1. color pop_When35pUR-nwehave
|Khtml: html:
_color push Black_(a) color pop79qki,URnifor35al li,andwhtml: html:
퍍_color push Black(b) color pop79qkj\<URnj?wherffe35jistherstindexwithkj6=URp 135(ifsuchanindexexists).Rhtml: html:荍color push Blackfa2. color pop_When35pURjnwehave
whtml: html:_color push Black_(a) color pop79qki,URnifor35al li>!n9,andhtml: html:_color push Black(b) color pop79qk! g<URn!,35andhtml: html:썍_color push Black(c) color pop79qk0V=URk1=:::uD=k!I{K cmsy8 1DP=qdUS05ţif35pjkg;USp 15ţif35p-kg. color push Black 2 color pop
Kc.color push Blackhtml:color push gray 0 color pop html: color pop[(Pro` of FirstmsuppSosethatpisnotadivisorofn.ThenpdoesnotdivideN@(n;kg)ifandonly if^pdividesneitherG ܍ n v~
ukfG|norG ܍ n v~ k6+1^$G&.$ByKummer'stheoremthisisequivXalenrttoki~niand(kŹ+1)i,URniOforalli.8Horwever,ifj{istherstindexwithkj\6=p 1,thenwrehave% {(kŹ+1)i,=fXUR8
ԍUR<UR:fd0DdifiUR