# $x^2-(p^4-16)y^2=p^2 \land x \mod (p^2-4) =2 \land x >0 \implies p | x,y$?

I wish to have a proof of $$x^2-(p^4-16)y^2=p^2 \land x \mod (p^2-4) = 2 \land x>0 \implies p | x,y$$ for primes $p$.

It is easily proved that for a counter-example, $p$ must be $\equiv 1 \mod 4$: from the first equation it follows that if $p$ does not divide $x$, then $(\frac{-1}{p}) = 1$, hence $p \equiv 1 \mod 4$.

But I am unable to prove that for $p \equiv 1 \mod 4$, there are only solutions with extra conditions as mentioned, where $p$ divides $x,y$. A counter-example is OK too, of course.

Examples and efforts so far, where I have split up the search for a counter-example by seeking (always existing) solutions for $x^2-(p^4-16)y^2=1$, and solutions for $x^2-(p^4-16)y^2=p^2$ where $p$ does not divide $x, y$, and then check whether $x \mod (p^2-4) = 2$ is possible:

When $x^2-(p^4-16)y^2=1$, then obviously $x^2 \mod (p^2-4) \equiv 1$. But what are the (possible) values for $x \mod (p^2-4)$?

I first thought that this can never be $\pm 1$ for the smallest solution, but from one of the partial answers I see that I was wrong: for $p=29$ the smallest solution gives $x \mod (p^2-4) =1$ .

Example 1:

$p=5$, the smallest solution for $... = 1$ is $x=605695, y=24544$; $x \mod 21 \equiv 13 \equiv -8$. Of course, for the next solution, $x_2 \mod (p^2-4) \equiv x_1^2 \equiv 1$. And the next one is again $\equiv -8$, and so forth.

Note: $x^2 \equiv 1 \mod 21$ gives $x \mod 21 \equiv \pm 1, \pm 8$.

Solutions for $...=p^2$ where $p$ does not divide $x$, give $x \mod 21 \equiv -2, -5$: $691^2-21 \cdot 28^2=25$; $691 \mod 21 = -2$ , and $10957^2-21 \cdot 28^2=25$; $10957\mod 21 = -5$. Multiplication by $1$ and $-8$ (as part of constructing all other solutions from the ones found) do not lead to one where $x \mod 21 \equiv 2$ (unless $p | x,y$ of course)$. Example 2:$p=13$, the smallest solution for$... = 1$is$x=1714005085317895182559, y=10144883927724859112$;$x \mod 165 \equiv 109 \equiv -56$. The next solution again is$\equiv 1$, then$\equiv -56$, etcetera. Note:$x^2 \equiv 1 \mod 165$gives$x \mod 165 \equiv \pm 1, \pm 34, \pm 56, \pm 76$. Solutions for$...=p^2$where$p$does not divide$x$, give$x \mod 165 \equiv -53, -2$: from solutions (146381426, 866405) and (649581787680043, 3844756292748). Multiplication by$1$and$-56$(as part of constructing all other solutions from the ones found) do not lead to one where$x \mod 21 \equiv 2$(again, unless we assume$p | x,y$)$.

• You could have $x=\pm 1$ if $y=0$. Do we require nonzero solutions? – Oscar Lanzi Jun 27 '18 at 11:56
• @OscarLanzi Yes please exclude trivial solutions like these – Maestro13 Jun 27 '18 at 12:03
• "I need to add that for the solutions for this second equation I require x,y to be co-prime (hence p does not divide x,y)." Both positive, too, maybe? – Oscar Lanzi Jun 30 '18 at 10:01
• Correct- both positive – Maestro13 Jun 30 '18 at 11:54

Update: Fixed incorrectly pasted value of $x_{641}$ and added a few more solutions.

There are at least five counter-examples (note that my search may not have been exhaustive, so smaller ones could exist). The table below lists the values of $p$ and $x$ (since $y$ can be computed from these two and including it would make the table unnecessarily wide):

$$\begin{array}{|l|l|} \hline p & x \\ \hline 17 & 213008070740687 \\ 41 & 870879127656939928113787319 \\ 97 & 10083873782748617936772480341106949378297314021219796666165588607 \\ 641 & x_{641} \\ 937 & x_{937} \\ \hline \end{array}$$

The value of $x$ corresponding to $p=641$ has $579$ decimal digits: 427646534402961781027145789918837939285691392138714792282852459374612979324825695693669914355863700239209336810908209681356270416796716850320235289335620082377462249476768747074873232460544874434722275625388774658019745544230329560583157094083209098723570357314076815220914717483657351159560400598800355165245603911804839233691468502679117513759884589593468171785683356282386931016071986818881847985935375230380820704838067930362661992988376805951747977341342123105794676799917874450015058939882919734980324750537060155504061516496791759049989307755510987369428664453094073643359

And finally $x_{937}$ is the $193$-digit number: 2766763201408142805699002603607382768361488866512185487519112560056602713684628027364427590616304623218846757823235445170446092862554381328586254664562804258792946140374215448195627785199577687

Update: After playing with the problem for a little more, my search found additional counter-examples. Unlike the previous ones, these do not correspond to smallest solution of the generalized Pell equation $x^2-(p^4-16)y^2=p^2$ but rather to one of the later ones.

$p=337$ works with $x$ of 2437 decimal digits: 2012548871657191981431611993069633640028438880682615048643985505215700083905319718762883664364382052210783496460789800652979574224765664149017287195517681416702307310683498541450600889177470452111355762720809239829700367964707518489892402922587019453520837916632075909342129458065883273976558850715898269483413751362979707302528472864220292460028238429252397079719532130535348902539070149295657923675580649254586307717008296045551277738828899719097311734306750997010385614364780726997165845182267506217121035346351579334997137899945453517512989553234123811688703233274284162965538969705737757579071690508215325168642868102421704164926145495590931194702112770833937740028636328453652593892988581612889614308475912113661768180605730238725030945292243535091309743366166999945816946385648183709109448145943296666269404450334746148277348730209017761228086096806014585794460669829594744450384201042792933542744310288714128498649328846782430633199868203980262604482564936659859827453693291117259759682236259868304492982011589083843174902743842461533465321347506239883649702636056457919485284672173953838024292945505696312281231468311054218420287662241312082783907746223975348633563382293899263799534145322440795806610253729393298849198312475249926967608357473228219377635789207569476686506182100142870155157046899310529398352083620937735331075447679760124682414421456785361468453752019069075761536225997844086567513693347277578538030285627139251417732922100604598716718325128695809917981939261452719819008802176993334984095139227076966961368507978806836962778808533395775044912356215126718175552286136757824113132034704871294223976151325757262084744611751872103825375303303331032282409735986873145768220318851289976258954268863072507912682919053521918773197913220927371753117862236364124168398613734762422896960291104124692160686236969658353342053038880198959531485381851236070242239434477210410622442071729798479606988380083698946139984721101568343379534784195212117081624105986769640795433306336820263669450398319898310961946081612169315426174790436122002166455840806223580851020941912410229035260266188137011692126438299688111664337876814690066586161667899847874768383615802665202152557377393590810430001339022149340817320586692728321660812480074135019374004207244268344227723539625992157973252815925052911797306025805512409742395854704993718208039438507374976701130278852164899403894096488636788673939219540519378134088093235559241507026607

For $p=521$, we get $x$ equal to 3713247976498568189340727102356887990784003862762132866042545819441263170558432336097020083159

$p=577$ works with a $3034$-digit monster of $x$: 3219653972154272759909544964386498558008405505404843731977069375796752023063517490709340315127470496061703512277632328693155912789353654512769387902305769107894092988901668136720628864190758351049906865458079921182271444897369720580642994810828659129712950582366849983657491386018435097216461734427753559386833263024817732966074151021118517880634576938525218312287881434638787555138798021649823725621589172706811016918551396441806878453939433833500442994166637443313575452920753849163175514502519213682690444420148810292966711474936803941393134175512302151529355261087498124565603170904426031675444226825891186146379791607511946598291485394003546174436965144937546465728574052335372615840611986698573551860614624976366526348300018313376628824087960597765776446884085783835679775404842668199962181182815598575709909188322893129798917652243263744195890388383574908271946140307701401882364351952640361348997337315010690004836030840109153031263694289789963420832738618330631556318826132583080222048192977021633629205944434140712560011335923977964187300605481363268363500994605645737017494226880103357471778021208567489128772913354465732226264468420991211916929843859869974985937944940594288873292393575112098152015782516964102286560252054289859702790684669261293261622626613833826642731283055899891610573915578331301051662924905546283252197201544019636075717615915857539603522323144835236652425374386520292810144849027417400041430579522434341420942374228329094482787203589688057230863829873270635685847053993512216494831044424608312431106087612050324500878142084225599037700355273178137998722849509147779081516433870437006401177375885132897767379200335846504670884914029217764466551825197017530550642915256070550752217413277951217101611218601408865162712605479439952703936350182348357985287678886061582913147687029921575804338829793259136920248431766629628444827401119981510678464881797245211755167298039888173236681267574088178236745357472227224841059867023676550232746570620472652716808746675723426791145912192665606279272721154615728599594286190931802453492136200043010967599199355972822383993314809033083173624525589182003197842234152863819349858196675576938070501819712147841089656260253281256683161654822671722796746477402499303426432770725946309965080604357540710918719363109121415120309161450806793254780201833048337463281982561693557781722876432938541428117874555502745454007217791080464367321986553549740039186770072728059743268955160531638957964976716236631401335682236371061671963556825304744315280793169385871063516324112514354186800880184453188218093329005772532442679887407101146136185406103312529371646707263437323585284427980548368125782157791505376162855514169231710309195122855999742686615867238989507100134250057476065135277613037206566835494154986613479918755669165102522742430737065693766923754864394362971653099216318726666267341354656855543238357859826059834679213845573758213032923801318775656185128214755232374019141305345958277917222469188655267515228405906734797611347583839624948546197572285414523329075268927

• I checked the first one and that looks OK to me indeed! How did you find these counter-examples? – Maestro13 Jul 3 '18 at 18:18
• Second one also looks Ok to me but the smallest solution for the third one that I found has a slightly different value: $1590487482748617936772480341106949378297314021219796666165588607$. Only the first couple of digits differ - one of us must have made a calculation error, but who? – Maestro13 Jul 4 '18 at 12:14
• I looked for solutions of the first (generalized Pell) equation and checked if they happen to satisfy the second one too. Initially, I was going to try to implement the method(s) described in Robertson's paper, but eventually ended up finding the PARI/GP one-liner which provided the answers with almost zero effort. – Peter Košinár Jul 4 '18 at 12:44
• @Maestro13 When I divided the square of your number by $(97^4-16)$, I got remainder of $34767459$ (which is not equal to $97^2$). Did you get something different? – Peter Košinár Jul 4 '18 at 12:50
• Apparently the calculation mistake was on my side :-) – Maestro13 Jul 4 '18 at 19:28

According to my calculation with PARI/GP , for the prime $$p=29$$ the smallest solution is $$x=511417665685259113593784321$$ $$y=608113496300320416961344$$ and we have $$x\equiv 1\mod 837$$

• And what about the solution for $=p^2$, is that $\equiv 2$? – Maestro13 Jun 30 '18 at 9:22
• I checked myself. The smallest solution for $=p^2$ is simply 29 times the one you found, hence one to be excluded. And $\mod p^2-4$, it is obviously equal to $29 \ne 2$. So not a requested solution. Or, in terms of the later added underlying question, the only way to find a solution for the second equation is, to multiply one for the first equation by $29$. – Maestro13 Jul 2 '18 at 17:16