Charles Babbage's Conjecture

The validity of the material on this page is questionable. In particular: In the light of the page Definition:Wolstenholme Prime, it is prudent to suspect everything on this page. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by resolving the issues. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Questionable}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Conjecture

$\dbinom {2 n - 1} {n - 1} - 1$ is divisible by $n^2$ if and only if $n$ is prime.

Refutation

The smallest counterexample is given by $16 \, 843$, which is the $1944$th prime number:

\(\ds \dbinom {2 \times 16 \, 843 - 1} {16 \, 843 - 1}\)

\(=\)

\(\ds \dbinom {32 \, 965} {16 \, 842}\)

while:

$16 \, 843^2 \nmid \dbinom {32 \, 965} {16 \, 482} - 1$

By making use of an on-line binomial coefficient calculator, the value of $\dbinom {32 \, 965} {16 \, 482} - 1$ was determined as being:

$6817357320588131450677228005719039720375978470068754954650937040829753832948113907724706732983714107$

$1403152125195364921431965205381247676501164330407145035473411656791273956401862383776012356220487837$

$6395724710224349419282950443680721152119603967013604779027005576298014793098530853262123948489689900$

$9873528822811986103467253863196636622630578681911939338812891009945458574273535367844675275442187048$

$3001601022509912673132576571969762602415408423661052032616281833544637680105879706040601631820651368$

$6578708688229535099452351437661343885887403911089167005623046988789631101475371724151294992598420670$

$7710663589692517728339291510196613913681320156392165653839866851742241202145924323003971023796506727$

$1755633429777411428584538028157994894649465316508359568625484091963147249818717027431775372837507204$

$0968243815208916285813498932260902145426578529960875971689087489899735626559394676502896595640363878$

$9012124576651002112409358734213538650771550351698852203107512285827443662062637477394489041615884831$

$2831305888482551376966155885484686606930352167446287418901998257781888127497533143522215830102534147$

$0975907413750226307652096930405341814759183124783676579100462836400634372289501280129900488588513800$

$5640097760974922640706562030944336758113975782095983361434080767227783820561643041056085084949954740$

$0825939030207788747414252540985614870899425157862690295639412331608194383430626997896544341365676622$

$5145740953429783903143062077430348038946221884608326275441539898970191767418824988256177426410974483$

$6740360655886978442767698733439634401440533116286451791941542351293943706448846613287596731708767794$

$2961646544874649948255855443847339165893881662734768490350175520592647389564444499125084684939222146$

$4685758810492969581408116755490191033937904324504341969555409197619459921168624012130968375402895663$

$9941368938005896732401310025543855947901911964749349140098581419617625541314331490647639413230183159$

$2171648216700860032541926924454599444405633996317815524271818588566782862119466412485322895046372752$

$4338061455981005895933638602276125784451862132657711866059002567485808514485472891840308396594014652$

$5491564672104634960625584413697250387968147424186672159758664842413205054949427150180353270017353577$

$6892371889897580525054388432866630109958914761539742272050785515223946152379756346336451940428071835$

$1938007150410180451284835444718577760474522978308426305356258884030668303859257791077891189591795798$

$8412311470839272905383391605872181628409221792190801102435214708732499181672524677347585539945487473$

$7826133136438234042112252143175135433464295547863478992688034090440094023620607971735068759640877452$

$8393895734015461093732123430444797052447330121291384342102425398425808582060846795589877356627175196$

$0348302703353845254604716834670911220315965955541224990000628086828970779364913404611596027840647896$

$6025166093820758006325727737281293968523189534644841218480049796994391804028546448651076939705917343$

$0723727821008024689012741964535095961442369821949592041690639071937135853188382262671191425213694511$

$5107266021282693090626440870799084353260473240325755400351523124348883070251245711984497166761758287$

$2824786443700924664740340326088134315737448977018451060447859017871109057813715077582961720578059226$

$2698704185860543585038468353914157226248976168380461732747376810773168695547473246673189854181532069$

$9140772812887967286977601113336624376536113572084566007491050865433882110663570768104407203209908301$

$2790923075638938844089893836679941084939951731276742920440033003822261776918178755842990937185506358$

$2182973601685644167141454223074379288578586212743581283706215500147004055240937861829227014965967160$

$1978836497019335618697498013752513509267519201930998493628848058382643592075409878927345120169995957$

$6874858477460821022118924578650770920804630790990273497531302767114539550468299061379033001161808914$

$7366667776296674847138637513857430459908475607662575724931138846092650633442547108737043510578566724$

$4838152928643229118475415527526489268061063553488586845178404619413959701997361913670649952931339497$

$8862271171160410553500148478075267469854855317322806971890606115742674492554750731402358142302280666$

$9567440520930278117994294845617856947819167993546530198547797525251003625980160913290313691231268055$

$3354074802306021718113291323415695024818079478968512755296052139177391896955611947945924271467973713$

$8386727033583938717627588501318625853647472865566740677473136393837108359939785595563243595395558688$

$2136997352114904489391181758519544712621870618950400137229977966603435187887066949819164544733492124$

$5857759068225978647046570270658923501823898958981501621833586912524389378252583393238289290338606124$

$2865606435005023883284720008420498823205203463108182320619595079450387028447844505963152423779537959$

$0350069472980760286149396680779940057152566514598472260041450234742959277905877127769600118893143345$

$0535205927564217396847747132378429857226545714199850554433682600372601783461302249672817700392499709$

$7990910389599438039551565716071116044020672164651549040230570204143375923862253439987542852911071374$

$6486007048095007394014540906018452352564291957547928419535491129293790387366376509192427778672673483$

$9367548103515555871922319269718941689167480039844435087884133770914814243946021444029176853512471214$

$8401408018271933675653767331812434460956258784430683294286022533694713047223997142844959160233829708$

$5141630844847717858400952452709311400051733553478659321309753974055940084975466070142585323388595453$

$9762106794412331621082537646912218427924487008462729544868035474699564541828202485921492894229462204$

$2878368343105571794899873845705210598191236508349308785894397149877012743545739740735638242383611695$

$7501060914558312615057761600584543522059402219244212064075564796316170398101304085636670752165720902$

$4567790221707803885835521971660312843650442293202144551130762389308334011617627506203313522849608863$

$1772662962074826885652137365000399913784106202067906456914978803844614086880213315586353345749613199$

$6783546211358484649856439716168324557125829021599304078502746627365938976921028967855997209273655271$

$1702039851340234884277363181596828985340562141532746245107306115228911466584264553297695994667019854$

$5154829120299500865648078440501555349247361143582776924409816202764097804688243858004588409701431455$

$2629626782202586033837283621448077599551830464738372563449648555567937144011114130204494180767089327$

$4081524371166664660210252305215557176756278917369070513378916766097913780286593408120653226297974813$

$3108137071185658141488758731231883099149220304612917279267555629070161505039052783348756708569411794$

$8029507407856925663980033275258504324065797747256642696610543726195902441218555106946394228405629526$

$8822755068964597947907994971286880796649071063518710925993280911346233331562420963563796785950168652$

$9458992261468088325602164583830153209063921779173733931269709651562639736464332459276186430953597653$

$3184876432071925829760579059661572844759997605387142483280534861934923699644302926496963607126580970$

$9009497328929728526913044887065004628381135797748856692282436604200890638289418254304896610704797612$

$3650364495371964733390826286892437844656002229815970009694080175272952922554086276706114845090463223$

$9266659838820163615302953926650758613525284036216964690342358675588796993365930720084195317104931916$

$2049635469548547517170694902356108592064252493648555250945964585951204008812447152562226892627003121$

$6996778369960959419382443388258312961300692801463821968291834865758497994256768052351163456574622521$

$6401890357576627384706071999492557034263283851555269321577344148421340202188200130625395352589630247$

$8395244946426989559783710173760610814116809258104013685434939673714413157886689869544478053477191167$

$5777538488597235510815898110578778132695052249059778486878489450856377760806051807735166878359343032$

$8220694129779984470095166633777376578485612263975774481422529449235959271382908211331201040335972320$

$0503127186260075050249664450531042714581256675248113092880353101375755347436905546149809268060260005$

$7324982799804950402881626166046704588228149702920062906033917627390523047557547413689322295106717364$

$9176944125446653201240004551813459260428658225118812303977906675688780112731913716082077159753552681$

$6389871164963219538307244857590737161603595661900047758902859426403565017360441476746594346479685882$

$1049373747844233783139284647118406494634867142164773483539455804636064930047279168581533757642110091$

$1547720316029172799319646126208983141889558812334426145927394319866523946141303222040801281118030872$

$7776081355753091122883216261541633472170787033346335214266751907063118397983923271747111764580618728$

$9401526069023251619586811043731445939014559895438057880491219611522444276075846282528014094674922059$

$8325211817235583713243717976084597161363895696620454497436892825793695038100291740629997034252150086$

$0723362062678045984943797806181806087890307909060463054205733952326622829913958199575437085658137238$

$6225349244540167129505953792502954181421488305496376257360245825885812764687504716976117340828941301$

$2437784025704945928668947208933044863501543769472460837640047020692753611067551230628100074710842652$

$1690261433424352826338323069812354734276457630528544121756143543970784212922871851371413657509673341$

$1233065451407268796975382657208041857448145235205154331881908749360691501900553419966795525729201498$

$1357344179915622837279588430312637420257707709713555834901968676469196357974708931614997577266988513$

$2229152723465638854841813714672071944818607309779071427163765129314689931521156266449188083482881944$

$2238878611370455367457908999507276773956575635966564860016987558614039291251400598830283778756203487$

$7416422799858812368220077448010633208340781634832807865410125939869053287418051504150529301189829926$

$3433734306712115619704629809828734541088722411826036488655667318390875186683338991522887389607101741$

$3878717780839079232941630712208170734262698347295121557681537402204893775141378239433624897002451619$

$5601465298132034493089186546407955353058581739765006274011357520217202202503227902258395637167195216$

$4313009026862797592121749256036139074576218209772176191913412114271397344876468250613205750073412654$

$2639095439113816358018707514639663585915868601414875909387108854137753317035571271277048338745104909$

$24115099068118365897802282114934359999$

$\blacksquare$

Source of Name

This entry was named for Charles Babbage.

Historical Note

The name Charles Babbage's Conjecture has been coined by $\mathsf{Pr} \infty \mathsf{fWiki}$ as a convenient label to apply to a statement whose full description is unwieldy.

Note that the name Babbage's Conjecture is already used in the literature to refer to a conjecture suggested by Dennis William Babbage.

According to David Wells's $1997$ work Curious and Interesting Numbers, 2nd ed., the refutation is the work of David Singmaster, who also determined that no other such counterexample exists for any $n$ less than $150 \, 000$.

However, this still needs to be corroborated by evidence on the internet.

Wells also suggests that any higher power of $16 \, 843$ is also a counterexample, which would be interesting, as it would suggest that, for example:

$16 \, 843^4 \divides \dbinom {2 \times 16 \, 843^2 - 1} {16 \, 843^2 - 1} - 1$

It appears prudent, therefore, to ascertain whether Wells is actually correct in his citation of $16 \, 843$ being the counterexample that Singmaster actually discovered.

Hence research is invited into the literature, to find the original work and to confirm what is claimed here.

Sources

• 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $16,843$
• 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $16,843$