elementary-number-theorypell-type-equations
I am trying to find the five smallest pairs of positive integers $p,q$ that satisfy the Pell's equation $p^2-321q^2 = 1$.
One obvious trivial solution is $p=1$ and $q=0$ , but this does not count. I am trying to find the five smallest pairs of positive integers $p,q$ that satisfy this equation. I would appreciate your help .
An important piece of the puzzle here is that the ratio must be exactly $\frac12$. This is non-trivial to get in its own right. To see how the Pell equation works into this, let's figure out exactly what this condition says.
If the total number of socks in the drawer is $s=r+b$, then the total number of ways of drawing two socks without replacement is $s(s-1)/2$, and the number of such ways with both socks red is $r(r-1)/2$. Clearing the fractions here, then, saying that the probability is exactly one half is saying that $s(s-1)=2r(r-1)$, with both $r$ and $s$ integers. But this is a quadratic equation, and we can solve it that way: $s^2-s=2r(r-1)$; $s=\frac12(1+\sqrt{1+8r(r-1)})$. For this to be an integer, we must have $1+8r(r-1)$ a perfect square (and note that since this quantity is odd, its square root will be odd if it's a square, so $s$ will automatically be an integer). In other words, there's some $t$ with $t^2=8r^2-8r+1$. But note that $(2r-1)^2 = 4r^2-4r+1$, so by taking $u=2r-1$, we have $t^2=2u^2-1$. This is the Pell equation that drives the original problem.
Contrariwise, working from solutions of $t^2=2u^2-1$, we can find $r$ and $s$ that satisfy the original problem; since $t$ must be odd (its square is), then $s=\frac12(1+t)$ is an integer. Any solution of this equation must also have $u$ odd (just look mod $4$), so $r=\frac12(1+u)$ is an integer.
Now, solving this problem involves looking at convergents to the continued fraction of $\sqrt{2}$; in particular, every other convergent will satisfy the equation. (The rest will satisfy $t^2=2u^2+1$.) The first few cases are $(t,u)=(1,1)$ (which corresponds to an impossible drawer), $(t,u)=(7,5)$, $(t,u)=(41,29)$, and $(t,u)=(239,169)$. So the smallest number of socks in the drawer is $s=4$, with $r=3$ red socks in it; convince yourself that the probability is exactly $\frac12$ here. (Hint: where can the one black sock be?)
To solve the other half of the problem, we need to find an answer where $r$ and $s$ have the same parity; this is equivalent to saying that $t$ and $u$ are the same $\pmod 4$. The next solution, $(t,u)=(41,29)$, satisfies this property; so a drawer with $s=21$ total socks, $r=15$ red socks, and $b=21-15=6$ blue socks is the solution here.
If $p^2− \frac{251934169}{4} q^2 = 1 $, then $4p^2− 251934169q^2 = 4 $, so that $q$ has to be even.
Let $q = 2y$ so that $4p^2− 251934169\cdot 4 y^2 = 4 $ or $p^2− 251934169 y^2 = 1 $ and this becomes a standard Pell equation.
After searching for a Pell equation solver that could solve this, I found http://www.numbertheory.org/php/pell.php which said that
the least solution of $u^2-251934169·v^2=1$ is (u,v)=(225271244990700943315267956280411800555634015051308090277884868604104962338540162508662780103851110134288923470733214492576705304921942447496877316432148755394149624610709778342253829532034182955585281785605125774062067042871533474548723189550080879461940755054931210785029037747926428769992333668074349218880978527807663394127680486193384843986997533304388501754725074957250497216933172269065473852746178843181608306140365685996039286536330244666823292214037380277106713895640581283369187712083172695225344399463019401537455882605714942067846468852520297222251755337316170041845823661624202782666250115734237819683042082985171526282800382222714576727626094980629885366352000131303132135359463108635521565410488112287912844686192672738472001947756812093648970418119040213989933215258586913997217342108856777957037627456499897383934170286644285878283503578561992303795946148570976156177701503287373115452930781765236053893727748799204417831966968237024161827983124601075826155762117660452380906950456102876389134502447701968296040064628681054852876640098371536019198418255253941528944307814328148190184143000799951889089084659644347638577183884192073467082108506523506372732340274528141456740473415969963650656773018158163222322270988303396424521240862140458260591486474043045092368034899520901292279521856198411310822116084681636806884280270173841934612885750400068863907732865349185857915555235934810570449154233256465716941270067608222665579808387449666859364948244303214692248884665160509209379252943392494272634976297214741913847533965479527154125323880743892254267831724482576916275662958095933387932932551059660582766222292883165493697748307219389789209133143531345455092189866850439804333199651752360242139683699342368412986247802850384829304599110060419091883992716219173015297451039403047743238488985860729267543533352329687314970438461416693387772967943131761604987413334536162985092790422123282237028624645785633489664726218957148609919685769428122222084852809562569214413965720771408729185099918424343296677568166613090433613515483031252901694323178595995462642028964386862010093420726769418355184234720946181775332737659395967587225532076407623909565596790910765885818561865412162538848363553668612714198691288861437047601157353591221118724976585902490459382998907534939868158790879001671152433044317432949761648923963614896693699457510715718361695625294634696966284878410574160929772400728092044256419270960522476326245255572559146175279700400659950509793788476378848175390369825427301273114735692514379330175924474553668351745584388982458068437797359188706503857643164095213477929089334214332342050356909188421399238606889543471922745845239071010651328302511512759263707483733323614395083737283232899508265127479172494312201913477981379407799842709252906180434716507141311051322982240657546127971114278462713116439134410377103157523161671298844486230796509326848933853071382190119442436807702852665446333225245223437120117269735297360569365484765265678599514845945070544634609637487148190908846353641866101791106162516313305822511866796089071796216876389782118935966244678804350508265429071175447438279751936690584484769952697448915336468581146844571603113602643709943866971797062017021207642033921312513697587999212884164536775768402206018046772509817554058217211657510926455226154119243190033360301765607288639334708843614852895130144204537103834220400026878753494472540566640552609407477709815083333874222841700725622211428144359211679202120655592804708419101143418091589880834113404679889876903100324371120800767782414611156383670868080765233711399358523011346075275028463738338742036397612554950891163082740807747720798395812396497715250419270439996118401688429363409408587403868552632449,
14192608484101852311652173245015908656804599176789443002894924495999549636714310791643897994105341662923337788807362492209151601295913400774106514453526713684300113833584020254065789648114268592736284956478181887539578184404968727535130675240301330680424045087937507751354783751843882083549961006487041762539143092240182267625673545543455936367146411970290305782054776154497199209337203912681883938910324043935778509782484042962801145769894029337234699854480354143198040854080038324908157243595282073438163655575224248176278517428229817251480464816158421625916354924041235208915540115080577922127171351419601521489833636713770490678523243460973684413305651071322894619250800870367143777158331968412485425107035913822330947567736802295289309310119051345239539416991493942015919622751790785348919038379805859227911049324217398997513740560122179284504743633281021356441339976860299787471756578513146889121257883460749829291521787806407625153692719275725372954170370022396315140061544307643175653776535400455073782043194286683651362868872913084605139896620681911829754951648855405035242954097123540546545699114503980773519800040686939458468363079503478112881810641405492312867968273945731622796829877056323659996692366270430039570246302826360217970167904052112666239140660239846400409281440873845501116446348007978493038509853751195440746244570564678705662263875503717637378479288532317999237973107560945322110329507371890363756609225345275053348896623790574378451171965349295601942657954603086798163818585160123133049105832566315756886174131977304383495738867259989933572107914654007602572072669886503835449434697082833959512274441463637591580987951456241751839753688294600046750422849927840261048311740759015102448579153671310998368053088014413525190580443197365032823977294039021848988011145065910397014584936450149791059595948730498821311193267054622077669604956790772519227683823436511355690914063750200890967538599655958474116254219092343844084126763004405544159971866399839778417472371540744843901169054419472383039900816397260964805188541414616285494763474041141378518475042644111271715236082099399166939856152460149713823550540711450666953940767069945152766271334212385420086229265163361958210608874053137385703689903131579849687810390459434530819888897316926006951015316039571670007909492659476534147543282568764219964830440993197525690257373171516463315610841446990538425316425355251031712246044841634387772586408427005184450884952092284031967616619098317229037204142888806862991799280665577744394701502355439865753451015144520995850646040168483054240045219151600299985495053865199334557347514401508695659852900307881024093654437140394704913020334654207296557171006143445535613450778534351554384994362657965164040526157761954009421379897594732901983494994792808653901666978465058145147354647254159740325889135516891795932511454135345954246797045832787125979302458944880231797844254718580918828915871316273175022436224022647959141841073343734570471214713851782861120193652913798107781606774103634812965681121606226667532526322123126746467720543222481394331092466461362151862939111283968719755841042222483184032785703070867059218255951365944496598450548638969450932368393283610523294144075386919088667617918737462345261757489235868698957598377417131105200698535366855674649415279001796791530769452086033364850542624709325984274768735921564813978980455723994052138769997183002925322064719114992191840357539339755443706277234339761275474258068517184163636886137772133041843474458907703473580758200124705007910905441490819887820473878036142169329356939728136901858192287740818406164859433087836097641719006150802492533584026676040865371473046576830869200861399986483430883990828196264177112291206269520)
Best Answer
Method suitable for hand calculations.
As in the other answer, the larger solutions come from powers of the matrix $$ A = \left( \begin{array}{cc} 215 & 3852 \\ 12 & 215 \\ \end{array} \right) $$ The entries in $A^2, A^3, A^4, A^5$ become quite large; still, the main diagonals have two equal numbers, and the determinants remain $1.$
The letter $A$ stands for Automorphism, this matrix (notice that the determinant is $1\;$) is the generator of the (oriented) automorphism group of the quadratic form $x^2 - 321 y^2.$
Method described by Prof. Lubin at Continued fraction of $\sqrt{67} - 4$
$$ \sqrt { 321} = 17 + \frac{ \sqrt {321} - 17 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {321} - 17 } = \frac{ \sqrt {321} + 17 }{32 } = 1 + \frac{ \sqrt {321} - 15 }{32 } $$ $$ \frac{ 32 }{ \sqrt {321} - 15 } = \frac{ \sqrt {321} + 15 }{3 } = 10 + \frac{ \sqrt {321} - 15 }{3 } $$ $$ \frac{ 3 }{ \sqrt {321} - 15 } = \frac{ \sqrt {321} + 15 }{32 } = 1 + \frac{ \sqrt {321} - 17 }{32 } $$ $$ \frac{ 32 }{ \sqrt {321} - 17 } = \frac{ \sqrt {321} + 17 }{1 } = 34 + \frac{ \sqrt {321} - 17 }{1 } $$
Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccc} & & 17 & & 1 & & 10 & & 1 & & 34 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 17 }{ 1 } & & \frac{ 18 }{ 1 } & & \frac{ 197 }{ 11 } & & \frac{ 215 }{ 12 } \\ \\ & 1 & & -32 & & 3 & & -32 & & 1 \end{array} $$
$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 321 \cdot 0^2 = 1 & \mbox{digit} & 17 \\ \frac{ 17 }{ 1 } & 17^2 - 321 \cdot 1^2 = -32 & \mbox{digit} & 1 \\ \frac{ 18 }{ 1 } & 18^2 - 321 \cdot 1^2 = 3 & \mbox{digit} & 10 \\ \frac{ 197 }{ 11 } & 197^2 - 321 \cdot 11^2 = -32 & \mbox{digit} & 1 \\ \frac{ 215 }{ 12 } & 215^2 - 321 \cdot 12^2 = 1 & \mbox{digit} & 34 \\ \end{array} $$