# Charles Babbage's Conjecture

## 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.