For two odd primes $p<q$, can we deduce positive integers $a,b$ solving $a^2+b^4=pq$ without trial & error (brute force)?

Question

Let us fix two primes $p,q$ with $2<p<q$. How can we find positive integers $a,b$ which solve the equation $a^2+b^4=pq$ without brute force?

Interestingly there exist sometimes two solutions:

• $5\cdot13=7^2+2^4=8^2+1^4$
• $5\cdot821=3^2+8^4=53^2+6^4$
• $17\cdot113=25^2+6^4=36^2+5^4$

In more rare cases I even obtain three solutions, e.g.:

• $73\cdot89=49^2+8^4=64^2+7^4=79^2+4^4$

Is there a systematic way to obtain the solutions $a,b$ directly? Or at least, can we establish a relationship between the two primes and these natural solutions? I generated a CSV file containing some more cases, which maybe help in finding patterns or connections between $p,q$ and $a,b$.

Can we anticipate (state in advance) how many positive integer solutions we will get depending on $p,q$?

Answer 1

Given $\quad a^2+b^4=pq\quad$ we can use a formula for generating Pythagorean triples where $C-A=2\qquad$ Here, $\quad A=4n^2-1\quad B=4n\quad C=4n^2+1.\qquad$ If we let $\quad b^4=4n\quad$ we find integer $n-values$ when $B\in\big\{2,4,6,8,\cdots\big\}$ These correspond to the triples

$$(63,16,65)\qquad (16383,256,16385)\qquad (419903,1296,419905)\\ (4194303,4096,4194305)\qquad (24999999,10000,25000001)\qquad \cdots$$

In these cases, we can see the $C$=values are composite and easily represented as $pq$, but whether or not $pq$ are prime must be determined for each case.

We can find more "candidates" but still have to check $pq$ for primality by using Euclid's formulas shown here as $ \qquad A=m^2-k^2\qquad B=2mk \qquad C=m^2+k^2.\qquad$ If we solve the $B$-function for $k$, we need only test a defined range of $m$=values to see which yield integers for $k$.

\begin{equation} B=2mk\implies k=\frac{B}{2m}\qquad\text{for}\qquad \bigg\lfloor \frac{1+\sqrt{2B+1}}{2}\bigg\rfloor \le m \le \frac{B}{2} \end{equation} The lower limit ensures $m>k$ and the upper limit ensures $m\ge 2$ $$B=16\implies\qquad \bigg\lfloor \frac{1+\sqrt{32+1}}{2}\bigg\rfloor =3 \le m \le \frac{16}{2}=8\\ \land \quad m\in\{8\}\implies k\in\{1\}$$ $$F(8,1)=(63,16,65)\qquad $$

This generates many non-primitives and a few more primitives where each $C$-value must be screened as above. Those primitives corresponding to the above $B$-values are.

$$f(8,1)=(63,16,65)\qquad f(128,1)=(16383,256,16385)\\ f(81,8)=(6497,1296,6625)\qquad f(648,1)=(419903,1296,419905)\\ f(2048,1)=(4194303,4096,4194305)\quad f(625,8)=(390561,10000,390689)\\ f(5000,1)=(24999999,10000,25000001)\qquad $$

Answer 2

With kind assistance I have received a useful hint for a direction to investigate, wich I would like to share with you all:

In the case that $p\equiv3\pmod4$ or $q\equiv3\pmod4$ no solution exist.

Let us set $p=r^2+s^2$ and $q=u^2+v^2$. If $p\equiv1\pmod4$ and $q\equiv1\pmod4$ we exactly obtain one solution $r>s>0$ for $p$ and one solution $u>v>0$ for $q$.

If we now have these unique solutions $p=r^2+s^2$ and $q=u^2+v^2$, then the product of both primes is $pq=(r^2+s^2)(u^2+v^2)=(ru+sv)^2+(rv-su)^2=(ru-sv)^2+(rv+su)^2$.

Consider $b^2=c$, other integer solutions for $pq=a^2+c^2=a^2+b^4$ do not exist, unless one of the four integers $ru+sv$, $|rv-su|$, $|ru-sv|$ and $rv+su$ is a perfect square.

To retrace what happens in practice, I generated variuos cases, where three solutions exist (feel free to download the CSV):

• $p\cdot q=233\cdot12409=256^2+41^4=1616^2+23^4=1681^2+16^4$
• $p\cdot q=89\cdot233=1^2+12^4=129^2+8^4=144^2+1^4$
• $p\cdot q=17\cdot4241=81^2+16^4=256^2+9^4=264^2+7^4$

In the first case we have $p=233=8^2+13^2$ and $q=12409=72^2+85^2$.

In the second case we have $p=89=5^2+8^2$ and $q=233=8^2+13^2$.

In the third case we have $p=17=1^2+4^2$ and $q=4241=4^2+65^2$.

Hypothetically, there could be four solutions, although so far I have only found these cases with a maximum of three solutions?