Method to solve diophantine $Ax^2-By^3=C$ or $Ax-By^3=C$

Question

Am doing a research where at a particular point i have to prove if $Ax^2-By^3=C$ or $Ax-By^3=C$ will give an integer solution and find some of the solutions. Letting $x^2$ in the first equation or $x$ in the second equation be $X$ then $y^3$ in both equations be $Y$ i tried solving $AX-BY=C$ using extended euclidean algorithm and yes $X_0$ and $Y_0$ can easily be found and using the replacing $X_k=X_0+kB$ and $Y_k=Y_0-kA$ then take a general $y^3=Y_0-kA$ it which is also equal to $y^3+kA=Y_0$ Is just like i have reduced all equations to a general form $Ax-By^3=C$ with it's counterparts being $x^2=X_0+kB$ or$x=X_0+kB$
Note: The the one without $x$ term looks much easier but am stack solving any of them any help would be highly appreciated

Answer 1

It is relatively easy to determine whether $Ax - By^3 = C$ has solutions, even for very large values of $A,B$ and $C$. Actually finding solutions may be difficult if $A$ has a large prime factor.

First, it is straightforward to reduce to a case where $A,B$ and $C$ are pairwise coprime (or to show no solution exists if $\gcd(A,B)$ does not divide $C$), so assume this has been done.

A solution to the equation exists if and only if there is a solution to the congruence $-By^3 \equiv C \pmod A$. Since $A$ and $B$ are coprime, this amounts to determining whether $CB^{-1}$ is a cubic residue$\bmod A$. This will be the case if and only if $CB^{-1}$ is a cubic residue$\bmod p^k$ for each prime power $p^k$ in the factorization of $A$.

So the problem is reduced to determining whether some number $n$ coprime to $p$ is a cubic residue$\bmod p^k$. There are three cases:

• If $p\equiv2\pmod3$, every $n$ coprime to $p$ is a cubic residue$\bmod p^k$.
• If $p = 3$ and $k=1$, every $n$ is a cubic residue$\bmod 3$. If $k \gt 1$, $n$ coprime to $3$ is a cubic residue$\bmod 3^k$ iff $n\equiv \pm1 \pmod 9$.
• If $p\equiv1\pmod3$, then $n$ coprime to $p$ is a cubic residue$\bmod p^k$ iff $n^{(p-1)/3}\equiv 1\pmod p$. For large $p$, this can be ascertained quickly by using repeated squaring.

To find a solution, you need to find a cube root of $n\bmod p^k$ for each prime power factor and combine them using the Chinese Remainder Theorem. Once you have a cube root$\bmod p$, you can find one$\bmod p^k$ using Hensel lifting. For $p\equiv2\pmod3$, finding a cube root is easy since $n^{(2p-1)/3}$ works; but for $p\equiv1\pmod 3$ there is no easy way to find that first cube root if $p$ is large.