Minimum of $n$? $123456789x^2 - 987654321y^2 =n$ ($x$,$y$ and $n$ are positive integers)

Question

What is the minimum of $n$?

$x$,$y$ and $n$ are positive integers, find the minimum of $n$, such that:

$123456789x^2 - 987654321y^2 =n$

Answer 1

Here is some partial progress.

As has already been observed in comments, $GCD(123456789,9876545321)=9$. So $9$ divides the answer.

The prime fractorizations of the nine digit numbers are $$123456789 = 3^2 \times 3607 \times 3803 \quad 987654321 = 3^2 \times 17^2 \times 379721.$$ The quadratic residue symbols are $$\left( \frac{123456789}{17} \right)=1 \quad \left( \frac{123456789}{379721} \right)=1 \quad \left( \frac{-987654321}{3607} \right)=-1 \quad \left( \frac{-987654321}{3803} \right)=-1 $$ So we must have $$\left( \frac{n}{17} \right) = 1 \quad \left( \frac{n}{379721} \right)=1 \quad \left( \frac{n}{3607} \right)=-1 \quad \left( \frac{n}{3803} \right)=-1. $$

The first number divisible by $9$ and obeying these equations is $117$, the next few are $342$, $468$ and $495$. I'm going to guess the answer is one of these.

---

As people have already started trying in the comments, one way to make $123456789 x^2 - 987654321 y^2$ small is to take $x/y$ very close to $\sqrt{987654321/123456789}$, and a good way to find rational approximations to this number is to use convergents of its continued fraction.

This continued fraction starts off $2+\frac{1}{1+\frac{1}{2+\frac{1}{\cdots}}}$. After the initial $2$, the remaining terms are periodic with period $3861006$. (This periodic part is palindromic, so you only need to compute half of it.) The convergents look like they are growing exponentially, with rate about $3.6^n$. With intelligent use of a large number library, it should be possible to run through the whole list, as long as we clear memory as we go. (Storing a couple of 8 million bit numbers and computing with them is fine, storing 4 million of them is not.) I'm not going to do this, though, it sounds too much like work.

An interesting hint is that the largest integer in that list of length $3861006$ is $3103897$, occurring in position $472622$. Very good rational approximations often occur just before very large terms, so I might try scanning down to that position to see if it happens to give one of the very small numbers above.

---

The answer is very likely $495$, occuring after $18576$ terms of the continued fraction. Since $x$ and $y$ probably have $20,000$ digits or so, I'm not going to list them, but in principal they should be computable using this method. (As I was writing this answer, I see that Douglas Staple has computed them.)

What I actually did was to find the smallest positive value of $123456789 x^2 - 987654321 y^2$ occurring for $(x,y)$ a convergent of the continued fraction. It is not quite guaranteed that this is the minimum for any $(x,y)$, but I'm not going to work harder. The key was remembering enough about how continued fractions work to realize I could compute the answer without storing any of those thousand digit numbers.

Let $a_0+ 1/(a_1+1/(a_2+1/(\cdots)))$ be a continued fraction with convergents $p_0/q_0$, $p_1/q_1$, etcetera. It is helpful to formally define $p_{-1}/q_{-1} = 1/0$ and $p_{-2}/q_{-2} = 0/1$. Then we have the recursion $$\begin{pmatrix} p_{i-1} & p_{i} \\ q_{i-1} & q_i \end{pmatrix} = \begin{pmatrix} p_{i-2} & p_{i-1} \\ q_{i-2} & q_{i-1} \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a_i \end{pmatrix} \quad (\ast)$$

We want to minimize $$\begin{pmatrix} p_i & q_i \end{pmatrix} \begin{pmatrix} 123456789 & 0 \\ 0 & -987654321 \end{pmatrix} \begin{pmatrix} p_i \\ q_i \end{pmatrix}$$ Note that this is the lower right entry of $$\begin{pmatrix} p_{i-1} & q_{i-1} \\ p_{i} & q_{i} \end{pmatrix} \begin{pmatrix} 123456789 & 0 \\ 0 & -987654321 \end{pmatrix} \begin{pmatrix} p_{i-1} & p_{i}\\ q_{i-1} & q_{i} \end{pmatrix} \quad (\dagger)$$

Using the recursion $(\ast)$ and its transpose, we have $$(\dagger) = \begin{pmatrix} 0 & 1 \\ 1 & a_i \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & a_0 \end{pmatrix} \begin{pmatrix} 123456789 & 0 \\ 0 & -987654321 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a_0 \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & a_i \end{pmatrix} \quad (\S)$$

The matrix products in $(\S)$ are called reduced quadratic forms, and they tend to be much smaller than $(x,y)$; only ten digits or so. I decided to just compute these. Here is my Mathematica code.

foo = ContinuedFraction[Sqrt[987654321/123456789]];

The variable foo is of the form $\{3, L \}$ where $L$ is a list containing the entire periodic part. I make this into a single list:

blah = Prepend[Last[foo], First[foo]];

Length[blah]
(* Output is 3861007 *)

(min = 10^10; negmin = -10^10; qq = {{123456789, 0}, {0, -987654321}}; b = 1;
 Do[
    (qq = {{-a, 1}, {1, 0}}.qq.{{-a, 1}, {1, 0}}; 
     If[qq[[1, 1]] > 0 && qq[[1, 1]] < min, (min = qq[[1, 1]]; Print[{min, b}])];
     If[qq[[1, 1]] < 0 && qq[[1, 1]] > negmin,(negmin = qq[[1, 1]]; Print[{negmin, b}])]; 
     b++;),
   {a, blah}])

I tested this code by using it to solve the Pell's equation $x^2-13 y^2=1$ but was too lazy to write a general module, I just altered the constants by hand.

The first few lines of output are {-493827165,1}, {123456780,2}, {123456465,4}. This indicates that the best negative and positive values found so far are -493827165 and 123456465, using $1$ and $4$ convergents respectively. Skipping a few, {68508,1636}, {-15228,3707}, ... then, finally, {495,18576}. After a number more lines, it finds the best negative value at {-225,472621}. I let it run to completion through the whole of blah, and it never did better than these.

Comparing my answer to Doug's, it looks like I might have a fence post error ($18576$ versus $18577$) but I am otherwise happy with it.

Answer 2

Checking the first 50000 convergents, the minimal solution I've found corresponds to the 18577th convergent. This has $n=495$, consistent with @David's answer. I did the calculation in PARI/GP, double-checking the solution $(n,x,y)$ with python. The values for $x$ and $y$ are pretty scary looking:

x=4796374766605282503351751872331201400923514120426944040967627635895376189601418923539122980895157374664840701673814442926552540950110675302241932397036814865796905552070726240909298020358907240712876027631647322548624116166278598207211011547039911490388065046726364851240786240562467619706111839428229492887119534077543062504528844364634429084617112712589998613538372632646378604177109793182506195813043013688120071995599323193029081409670048794508288607174522431393551581158558427298005457565041698052146269574901121936462960380240600575759622236478905582105658997024956906688655138326553310731328347782142203140496025298736391110641341918163225508533166231994089466007836295263362737010739445853682313066216318858915104915054082818901309962893599148888908463393887875683817371433497875955581790796715649286641999079900837031462064566582174974031560254535548966225036875388858154888745956910395100248147770918072510598807399461114514401727433139642591126885962029568842037358345656940944393297517269542962094981260534550443901317030039502623582107694568383203769486945394903721597154012301854613011837845226306301324794958637108921073597009648097428310677706603949270173152625046664079731920432970257342582578959326926434443862393342786359445295797242165763797571438374279547953126950618739121129649014745039342479783642015047707732383633174360075154898478366066961890465534999423196794196390435368874070758131640004751257941381389752339450145469787164985568191325100341281692658878664153249898882691360291958275209811406444142072282005346386511860400218419420644334391530788357432259542173620708561887159405383197983661659836142502078580437827863965446035100818287640465637842612829485733666840425353102856036719869507009388178428651136411102969764640891892438976138713103700048126390276890532033399956490131903143025319328750012377694310924560860559997368111699463640197364829418189624766781718349859466954556900122179789891280991191950439543052613839091244645254552209407747021747392838011796247603110851718541166876919436242891309039501135586164266406814368865660447179235222014341033133477075882322372419355029959035062552201387385130615649432892230377378796661117665448920554938459188632960110096508361887429069685150970111247580638130231825953322118852961337450435705493485942954415176560172855883991828618553244017499025490630574390447778377797948031638415868175605911894990895505514669138287382592381002931895524455005501086070531121579702736810630486473539433383559812185698590289975115507650221238391948036688269113824823132757493777534152688726244793416319781405690423201448687281477142177996675141914555985724360936569454149914166182126856547916262829685792432037430347834367772925519944920031179592741414867646898328182168549393232028282899638088511076934204572717947817314405822567728979390080528976147889560900169462086769838975394565609204376076394224931675675478377253453904652258123449838462135733101031254142579028433828400248928854764368899784494853288531782749230757625069671863810249108734982704606768624912018410394798302564495797370400220686019475224885900683867148942517907559760432470720584079626650390406173572951485631992388031235915732491347981126946417497850466907767735568954133752100451069588569888840916423142370777302742719984664482176424185168009139946482644845818044035741006465529606278696834968060129881416869083817218270806086777689501146051602335724225849858931294629695819435224150158399036452058129571903139836740395602837366049422506043207780424579804464502359436314914935286140328283153643706158533273263315592983527505192619774421807765179786080420150513656002134659234087987608277609468226847743728323678428853844690139327042878318709516634359277016708089865749636396934480600765157725448780424355909447760397090437974233673821354407187804530115665594452164482972837236319797216326916201759521254823653593699289136902727192316095641194480546200804532908239790999683931963821259587921849015848858361006355298476913354445153959160724878185422816680344177937528749660715207862433472233906061338837453108489440005931655028328274057664920454644408681175818444081061963801092223913977172997175477111304604640829993734949924953616778790972901631671332446134685467868959160028423655663198135071300874796984286112394014664061979033035773701400883742702960712563001760024954375920239314497888550074306844737136247726137680752773705343148129194878559555822939924412055236438331095688396431923858326877004943669211479531214587557845042068454183903171621216209151204862899991298425278691772548801084527005446886367844704922168995016425364252883581201211153365162706829984950138124069228915417237420027921250846131922243446452492501966746856019703923374597494785770430815877387396643664232300734642972044754959073813941928310188575487523817143289793872137719772538422884034603969978449842704468224183792767966199974390391035165393774820657036555846608778429846434093892441739048623607399422631841216608608808409349385454628166458354389814444299927054562909822242797442873851361516178837976734450965299967151212100391630177011766453469564478407481425537089857007924508926144281248857578994211514312145466590800115002080485187561462190176420515254054272067780347662940961487185722652548969748772388624680754780353526315495864194367002648640427401488936847908919277973778767844906273309876081735620764174197666080038695010061021572331794286120497980420484099505701655221487739049496043747759609490003097948869902988348728187860978277551733148621492540696794141751547015214178432692304956581334490848073936030030246896653229993401807007384299915799824207616881896436015384141801220942336433592872333964924171296991475946299100472858821080723361507593534870528839747235388888493635435626508348141027766353857480492814188213831596400580722476499930810487614943707174611848737618939787655521514267287211443894721226045303368023774637842147447432203080791339450226500897356934057360454714093572780877945075002854569163779384425785320831109094504498698033746130421981890578940743777640729993475143347957825500045540271621808269867618238646430080394381387043154434352857732235732702325966893434500347446622465473310094503868473817341767295000091293167385027239060722714391010006183519380610247775299658583043105786808167052469075824960559791940261094728973961599324540009156496742230568384636424844964931005291116083508493667535897492777523126106778828299095625011625636461997959947801367875956607483017940366204829916481080558536502210714784926126173740481145529875906872169572648674397670757832637183706490085798855457740102735463303411286114924589826503579272190726413802930946083533948191499019996600320305947631398348260100744998614722687792878996456551680219696029103854413247593870662402512282980163980269368742516153331324853416947475804656804422123702426773749600673764115424856955764274062483879436777290251632335331379481277781400955538399221450188918837661950924569013340987944789335092797995624833455174736552691418840673204811014281452914705647075707048640213084577642498978975335467654156241859334626800527393608885050682953490367992772559541450116744258150252593974293348193534047726145586591615196400419604393600941386340141043983064782077456867773435179149625708133130641820872442868289708902716582360882845469306265524472166675386777163980821116334656100655869851044483388844756288414959681122854385543723285032608506675930977314937015198707263830222082573603037308029091202735370958823128581535738258079985128399363210647560006250365562284844681026869554329131885723063561991628999593536426513986669151129783302445015108642500344397592715099276730485558644663246274543883198107437351636314612670793447905885365960093524565305886041372017813204680441481063992760315366187511211972195302300798192860242965661807781703685307682549496356593159580413104657303048043924977895215761348350716920818176570626979687942863148877806099239386163015512638250533308236036374885850571914618453464837748833150458125720605955316605137204703941708539416725858775026659173727049362616006752314407796102062122077525197645006996792789303171973586506190624067152402696734006464256019809219658867064203359084335777667503580704036149203089873370911459299924544810397685397343919575182309824734231471444017025222036246221437903255613974861597878233676500762393256982868140313044480670759910811119097269944068691221223030788282987185943823178473021776661723341077753772947060775064837963776696038392161385318141338354043992970486141384974686731688467489329481466481027931325595259678395604067440768986723512110172107800714914273058287203552637579610501752875552165897534298114964885105548895001131148144819214199601188451816962922444332922838208727675714943425525529556185789057258335881405562983836947537516991304190958410514740211779923526456951189138335057350664024017683239657007717248499940478202030098526893590264904311263098771157226405790205911907754613407112544661482382957538570167564878504460566145683301254171114432549081798615208230773191666670057590546135705976794185908963055337853936791213729971276562167032461011602009778508771017447312054403791552466226423835202026542171441622270789155154545657328334465328172822495971062303567176883686245737448241851298479588733603547879635022009379716863981536594619991818980809052535107566049682407888357519018722241682078832599509474831224781513049014303441529935497976755844872476577901867241495292962856192083482688073810618302164018875100495570478156740924132693054332943967058589845523196657477173621762356898321295448764635215980677404625874505820791631409362669604298803606083022198957502428402102256950596847770305377630567477796264235411789354450439544518474493623124

y=1695774553562946861295259501185056916256944242172216626679092625881897531414164118050741057657721400429366054069593674925627385180460318164389471129155364372958213331714132453232324544818836245365128245079431272004151217935509723546830387185988582376662163002087012695954430617554877943127124146851455866770446121763445060762722398313238658201000195296955631807764310993221047022064098591376644904700284817649458764712735697622338588320080400985626390555222061429366131136345404059451677516539370271405033339519502123707254742643429654681607656337059170622288324702587077827918357339919282276548715981858991622489557370978659092013639664846187716062671764050045364779330341661240083844420203725226689155240966038920426750772295493447834448282984890024068837678660894515597545760212044500674993018015746901125065516600223891289427404366408478336391264592127121722245461776044147898393702269141964071154787829741225592498178844153210180795645192387535571499439643610073122941693334305848609508433531301834168666697608488718854026760170462502973309492095796848945247083671318632495065173899951112731078483956316002614381110712048853798006838144117357027293849652700869046425168142527200971932316921919608119588749140686228707754096500093558998664586326082009659440321537884868234486241593220528967592215083877323699194791392041715561061400076804647339209854727966423920207363638892602181762316261013785748159327978865609750934149204398370487639335012126314534470578018969776565935310459306314803756823838421881444414661356460902941048164812975561935175809026998255539107176833313317513848972730605036528904756917917864264902712037229787356315803900311513359786223608482257691077037880232467871241969148076333688947567209394797406433806660995567873388667276825508214841751661647730697145307317016997539461218641524177208768109440134674461055400662353755835428905704325653160205301583675197004968093428290198832117478224660829783958947562905474282201744241084676676543633182138198357307528229481124081557858028485617050683358526740426977516100928013220369361177924450245518512802115634303605538086366847503401952501889351751347444182614277348459432814949325665857676760751693205045721062696295104826218894948596229418777028886530249319276872384526533941937408603273040769542028000793478208353516677108811516268366097624991024558935382393795944777838328950249993362895074078016897617633090732058461651022773106146535194990169301668454906425271826346211463415120817036610064942144937003171854574120198145075068929133819250413320590038956071872730642395019763779169712309125948254599435495435608476259605067956306515270451343203196266642823722333404825499725708613166595776774705714930256452120683238239851508260272847521387459699223169310380141525257247207433859869993026921141311688323610163653312292588207326116606392674624700847608878560184193962782630562683827458041723382761179507905939735429213510382544824842893690046753351839165715121419204049642688714403852408546028220325567578394079453782952651309666878133548903354887553854168083826353325222439649475048435096999449034876832127641865926366487696294391428262625606965801306659333635604062094444545652712901267857981355006298911452153585599631496023545425046426987421850742570910501654552097486639577527760602585394640863779867493057028060701871646759654631186399456945933176060936791147657582597534893475095065179290604093894136327551790899932126912359421389785015560184032177210692491297473621103888131485397753373619596865538607132182153472462639381476379989225041002771838126353934452832688913807908780757178275574873154314846702416933718771521398995888684949885389379373178340915534328910674498208594953372721040478265802412787885082677140599389965016913574066675534477277445394190862311664764248080258974507682190038373384037614945473223921955908875722558904828061219721209914284743392414796590445002311227008928900950287537574293246339622932021795694590156297215519133613670562897216280049507429545095020820566565741553868160157715266567815092214911307328011059450931976153867795957579028009942363933839827104228749841189262464880809558800967941862082146587611945073499107686634105022747063555649778129276716724515767777242804505972229956956715589721123269704377436720107113384560057709076741692743430927474578960124462312987015226432500457781194592017985640304122603706641348167314181129889865045509935622004572787774986714180152134178565313620408505159452407851904954012028629085653599396323018541552886716883559944999337495454349741893231745955475339403549769308529112492783336579730677856608328825586962553707654477517949150592295643262052739951585551975943880507122650498545478952301600333288510677578600075062045140677282154197263107250890440391259314054145266913639433749838305345396582921169345689291279846923293252748600408705749338743683268442234003919562665815859004784266502544654479581094803754576328747749738232958467560382569099166404162057015921872305636117736083523593524964092131513810842935980682858339747197998409753957288826129839183441563320045020838569657523659722211492093665146015781661840630389700932420466743087041373323604107817373417595047861764692470843495095150057147605937109749178958907472278937061526486389053096197117858191493508681560376945614027820534450370270573147995412970162363264102781179610095625766197189564152078021238005147248162341611513114222078310967847976370171547747943236269686996274562446281231167486471209296262457157832310879644498948195147503286281870211620095152693032170775590318554010870347680452667433612081872540390763097600090637792977767060643487828758955056780907280027721851576255161684087866084536325218082971905206950577651432659170495882702182406706424479449827380985256738257666473340444344114046478748510607114848564369109170817236031652995944518985296224732932249999696686631044229802127510922451635210311152903045239279731579463953019048667747894394319511192799336558027048001718540106369215010046125140842296320085236699146756212865190222140491616629379669737074715671688599071970236175676968014520280238403826268415503604831067072134175860994557581705670745140199521779653018274078026600598896082179545055890695784542049334948509981696254543220437795419891796382783668569907817476416268361812088972184596274611370718382886710947304958488078957307791506587385903229223836593789731988707892878084153731834986483336827128854447395159032825808759950073028839962619587933798332644173778276508910005703239119867861252178123624530517411215150924375058000505451046194597033887657021779729770035285099973229104125946031107744305039900896709780631501893024897573488886574691075184056589874409068083307839797160172478651300721516338805276659138755545180317232487639129848150630629572847838818906395483459772077729297274584885396905589177781464020859622506380219130192216752486653948512649231669200598942270289885832535089179147765734679446339916180559944786135586908378092664902113447761773375789432041764945404647607097742221297253810432073697458940830180324434881602711959842447341970054228846565303599057331236420571347234474139019422400429010402259670317309507449796490347864859684680814407563282464047759197265554711767207514512625408395552553670776782206106276915629475337818995132641927741914351650986583007965150066284265547114011157111779827087174025610907926527400079071022768903159131501249508348309671914209073255212696142436820530821139286377399446782687324660174555034439875378737066968477463750798919722673383632483105040594773065311633355586044378015905094878523589437077788246285538985941404802828899012143327065126509798268958933455497358942904079514797758315000371465379721354157664601577832012287739403788683653745919813667705694855127197670950049914829017119184604323649568120498718488871277835278145859518126846782433441017333549012139441843135740177371028563670623868555841715033180756356569614285337848385872431173353072444491380467005016175953423406506582496970249093356761613450882357520134703303390072220160882937829617742073888595885748536572681682888337355047618761483183186585901228316333553135542062567554607420907134496443984577439918860583054657564077763689472849320652611535678435340258501481587254763848269263162987032963553802885106077146140886129168129307498933474625972537236393100834203179141205887335842853743054369100998784866789186115254641474625323701483919104631843411566150848901765516726823425473337148238848602605829414056570681452320125256226244665639844102529883417609863398257427543535109666977848130315175874009540534605802753487192997024055629357494608289988513424589777094401686514369254342858456797081524626207474850952339111394583589890868414885499311141023797982427215020425849682516864167971759748157356338261476526756638920195576436716905281152668038776036006307884191661772679012993051409623805607517205728197423809695524242997260154496562348058615715711573559194550269573071202566396522318271184819367192631768371024184929776355422998814073055526663889383129277599593328635010699576594898084699081574031249329631844908024706407740150265264464767185173609014209936445203647321124600443813534386328471573265126021213717546116315374711166869019673159115918167859711347583650921590410033497871527515657314027688984488684001103598906216459754538696239012071923531696829683707508577378583990046080995443610228567211931291886443930452500288221603355112367729483067655980678063808301467334448205617796899454815113205420493555508730268622028695412849844974518736141914681509927768525543652647989659134210446451196259221857920309429800619235884156600900040652400624455871252094460001225767045599638527301022983454119618146569514566151633660500376359235185648081937164287925383

Answer 3

I personally like to think in terms of Conway's topograph. One observation in the first chapter of Conway's The Sensual (Quadratic) Forms is the fact that the smallest values (both positive and negative) of an indefinite binary quadratic form can be found along the "river". So one way to answer this question is to move along the river and examine values we encounter.

Let $f(x,y) = 123456789x^2 - 987654321y^2$. We know one set of values along the river: $$\{ f(1,0), f(1,1), f(0,1) \} = \{ 123456789, -864197532,-987654321 \}$$ The set of values to the right of $\{ a, b, c \}$, where $a > 0$ and $b < 0$, is either $\{ c, b, 2(b+c) - a \}$ if $c > 0$ or $\{ a, c, 2(a+c) - b \}$ if $c < 0$. There are only finitely many triples we can get this way, i.e. the river is periodic.

How do we know it is time to stop? We can either iterate until the initial triple (or its permutation) shows up again or we can cheat by making use of the fact that the period is 3861006. In the language of Conway's topograph, there are 3861006 instances of $c$ becoming positive before the river repeats itself.

Here is a naive Mathematica implementation of the algorithm:

counter = 0;

conwayRiver[{a_?Positive, b_?Negative, c_}] := If[c > 0, counter++; {c, b, 2 (b + c) - a}, {a, c, 2 (a + c) - b}];

list = NestWhileList[conwayRiver, {a, b, c}, counter < 4000000 &];

positiveList = Select[Flatten[list], Positive];

Min[positiveList]

The whole thing takes about 3 minutes on my laptop, so it is definitely less efficient than the approach using continued fractions. However, Conway's topograph is very versatile. For example, it also provides a straightforward algorithm to solve the representation problem: given an integer $n$, to decide if it is a value of the quadratic form.