7
$\begingroup$

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$)$.

$\endgroup$
  • $\begingroup$ You could have $x=\pm 1$ if $y=0$. Do we require nonzero solutions? $\endgroup$ – Oscar Lanzi Jun 27 '18 at 11:56
  • $\begingroup$ @OscarLanzi Yes please exclude trivial solutions like these $\endgroup$ – Maestro13 Jun 27 '18 at 12:03
  • $\begingroup$ "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? $\endgroup$ – Oscar Lanzi Jun 30 '18 at 10:01
  • $\begingroup$ Correct- both positive $\endgroup$ – Maestro13 Jun 30 '18 at 11:54
1
+200
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I checked the first one and that looks OK to me indeed! How did you find these counter-examples? $\endgroup$ – Maestro13 Jul 3 '18 at 18:18
  • $\begingroup$ 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? $\endgroup$ – Maestro13 Jul 4 '18 at 12:14
  • $\begingroup$ 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. $\endgroup$ – Peter Košinár Jul 4 '18 at 12:44
  • $\begingroup$ @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? $\endgroup$ – Peter Košinár Jul 4 '18 at 12:50
  • $\begingroup$ Apparently the calculation mistake was on my side :-) $\endgroup$ – Maestro13 Jul 4 '18 at 19:28
4
$\begingroup$

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$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ And what about the solution for $=p^2$, is that $\equiv 2$? $\endgroup$ – Maestro13 Jun 30 '18 at 9:22
  • $\begingroup$ 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$. $\endgroup$ – Maestro13 Jul 2 '18 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.