6
$\begingroup$

Problem. Let $a$ be a positive integer that is not a perfect cube. Show that the Diophantine equation $(xz+1)(yz+1)=az^{3}+1$ has no solutions in positive integers $x, y, z$ with $z > a^{2}+2a$.

If this result is true, we can prove that for a given integer $a$, $a \not= m^3$, there are finitely many Fermat pseudoprimes of the form $ap^{3}+1$ to any base $b>1$ where $p$ runs through the primes.

Theorem 1. Let $n = ap^{3}+1$, $a \not = m^3$, $p > a^2+2a$ is prime. If there exists an integer $b$ such that $b^{n-1} \equiv 1 \ ($mod $\ n)$ and $b^{a} \not\equiv 1 \ ($mod $\ n)$ then $n$ is prime.

Proof. It can be shown that if $p \ | \ \phi(n)$ then $n=(sp+1)(tp+1)$ for some integer $sp+1$ and prime $tp+1$. Because the Diophantine equation $(sp+1)(tp+1)=ap^3+1$ has no solutions in positive integers $s, t$ when $p > a^2 +2a$, we must have $s = 0$. Therefore if $p \ | \ \phi(n)$, $n = tp+1$ is prime. Assume $n$ is composite, $b^{n-1} \equiv 1 \ ($mod $\ n)$ and $b^{a} \not\equiv 1 \ ($mod $\ n)$, we have $ord_n b \ | \ \phi(n)$. If $p \ | \ ord_n b$, then $p \ | \ \phi(n)$, a contradiction because $n$ is assumed composite therefore $ p \ \not | \ ord_n b$. We also have $ord_n b \ | \ n-1 = ap^3$. Because $ p \ \not | \ ord_n b$, we must have $ ord_n b \ | \ a$. Hence $b^a \ \equiv 1 \ (mod \ n)$ which contradicts the hypothesis therefore $n$ must be prime.

Remark. For all $ n > b^a$, we have $b^a \ \not\equiv 1 \ (mod \ n)$ therefore there are finitely many Fermat pseudoprimes of the form $ap^3+1$ for a given positive integer $a$ that is not a perfect cube.

A lengthy and incomplete solution to this problem can be found here https://math.stackexchange.com/questions/3842292/prove-that-the-diophantine-equation-xz1yz1-az3-1-has-no-solutions-in

$\endgroup$
3
  • $\begingroup$ my solution was complete. The discussion split naturally across $a^{2/3}$ which was not an integer because $a$ itself was not a cube. The reason for doing it this way was computer modelling with relatively small values of the parameters, in which it was obvious that some quantity increased up until $a^{2/3}$ and then decreased past $a^{2/3}$ Computers don't prove things, but they may show patterns that can then be proved. $\endgroup$
    – Will Jagy
    Commented Mar 20, 2021 at 16:36
  • $\begingroup$ Found your email of October 21. On October 22 I sent you a Latex pdf with a bit more detail. Again, if it does not work for you, I suggest you program the problem with small values of $a.$ I defined letters $w,t$ with $w^2 =x^2 y^2 + 4a (x+y)$ and $t = \frac{w-xy}{2}.$ Then proofs $t \leq a-1.$ Next, when $a^{2/3} < t \leq a-1$ we find $z < a^{4/3}.$ Third, when $2 \leq t <a^{2/3} $ we find $z < \frac{a^2+a}{2}.$ Fourth, when $t=1,$ we find $z \leq a^2+2a.$ Nothing easy or quick about this; if necessary, get help to program this $\endgroup$
    – Will Jagy
    Commented Mar 20, 2021 at 17:22
  • $\begingroup$ I finally figured your proof out. Have made it concise below $\endgroup$
    – ASP
    Commented Mar 29, 2021 at 10:46

1 Answer 1

6
$\begingroup$

The given equation $(xz+1)(yz+1)=az^3+1$ can be rewritten as $az^2-xyz-(x+y)=0$. We shall show that for any solution $(x,y,z)$, we have $z \le a^2+2a. \ $ Note that $z \ | \ x+y$, therefore $z \le x+y. \ $ Treating $x, y$ as constants, the only positive solution for $z \ $ is \begin{equation} z = \frac{xy+\sqrt{x^2y^2+4a(x+y)}} {2a} \end{equation} In order for $z$ to be rational, the discriminant must be a perfect square. Therefore $w^2 = x^2y^2+4a(x+y)$. We see that $w > xy$ and $w \equiv xy \ ( $mod$ \ 2)$. We can write $w = xy + 2t$, $t > 0$. Substituting $w$ above, $(xy+2t)^2 = x^2y^2+4a(x+y)$. Expanding and simplifying, $txy - ax - ay +t^2 = 0$. Multiplying through by $t$ and factoring, $(tx-a)(ty-a)=a^2 - t^3$. We must have $t \le a-1$ otherwise $RHS<0$ and $LHS \ge 0$. Because $a$ is not a perfect cube, $a^2 - t^3 \not = 0$. The remainder of the proof utilizes the result: If $ab = c \ $ where $a,b, c \not = 0$ are integers then $a+b \le c+1$ if $c>0$ and $a+b \le -(c+1)$ if $c < 0$. We now consider two cases:

Case $1: \ $ $ a^2 - t^3 >0 \ ;$ Using the result above on the factored equation, we have $(tx-a)+(ty-a) \le a^2 - t^3+1 \le a^2$. Hence, $z \le x+y \le (a^2+2a)/t \le a^2+2a \\\\$.

Case $2: \ $ $ a^2 - t^3 < 0 \ ;$ As in case $1$, we have $(tx-a)+(ty-a) \le t^3 - a^2-1 \ $, $x+y \le t^2 - (a^2-2a+1)/t < t^2$. Hence , $z \le x+y < t^2 \le (a-1)^2 < a^2 +2a$

$\endgroup$
2
  • $\begingroup$ good. Two typos in this , $t^2xy - tax - tay +t^2 = 0$. should say $t^2xy - tax - tay +t^3 = 0$. I see what you did now, in the last line you don't care about the stronger $a^{4/3}$ bound available for this case, you settle for the value at $t=a-1$ $\endgroup$
    – Will Jagy
    Commented Mar 29, 2021 at 16:43
  • $\begingroup$ Fixed the typo. Yea I made use of the inequality $t \le a-1$ $\endgroup$
    – ASP
    Commented Mar 30, 2021 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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