Simple Hyperbolic Diophantine Equation
Problem
Given the integers $A, B, C, D$, find a pair of $(x,y)$ such that it satisfies the equation $Axy + Bx + Cy = D$.
For example, $2xy + 5x + 56y = -7$ has a solution $(x,y) = (-27,64)$.
Hyperbolic equations are usually of form $Ax^2 + By^2 + Cxy + Dx + Ey = F$. Here we don’t have coefficients of $x^2$ and $y^2$. That’s why we are calling it “Simple”.
So how do we tackle the problem? First we will rewrite the equation to make it easier to approach.
Rewriting The Equation
$Axy + Bx + Cy = D$
$A^2xy + ABx + ACy = AD$, Multiply A with both sides
$A^2xy + ABx + ACy + BC = AD + BC$, Add BC to both sides
$Ax ( Ay + B ) + C ( Ay + B ) = AD + BC$,
$\therefore (Ax + C) (Ay + B) = AD + BC$
Now that we have rewritten the equation, we can see that the problem has two cases. We will handle each case separately.
When $AD + BC = 0$
When $AD + BC = 0$, our equation becomes $(Ax + C)(Ay + B) = 0$. So we need to have either $(Ax + C) = 0$ or $(Ay+B) = 0$ to satisfy the equation.
So we have two possible formation of solutions. When $(Ax+C) = 0$, we have $x = \frac{-C}{A}$ and $y$ any integer value. When $(Ay+B)=0$, we have $y = \frac{-B}{A}$ and $x$ any integer value.
So, $(x,y) = (\frac{-C}{A},k)$ or $(k,\frac{-B}{A})$, where $k$ is any integer. What if it is not possible to divide $-C$ or $-B$ with $A$? Then there is no solution of that formation.
When $AD + BC \neq 0$
Let $P = AD+BC$. Since $(Ax + C)(Ay+B) = P$, $(Ax+C)$ and $(Ay+B)$ must be divisors of $P$. Let $d_1, d_2, d_3 … d_n$ be divisors of $P$. Then for each divisor $d_i$, if $(Ax + C) = d_i$ then $(Ay + B) = \frac{P}{d_i}$, so that we get $P$ when we multiply them.
$(Ax + C) = d_i$
$Ax = d_i – C$
$\therefore x = \frac{d_i – C}{A}$
$(Ay+B) = \frac{P}{d_i}$
$Ay = \frac{P}{d_i} – B$
$Ay = \frac{P – Bd_i}{d_i}$
$\therefore y = \frac{P – Bd_i}{Ad_i}$
Therefore for each divisor $d_i$, we have $(x,y) = ( \frac{d_i – C}{A}, \frac{P – Bd_i}{Ad_i} )$. This solution is valid only if we get integer values for $(x,y)$.
Careful when calculating divisors of $P$. In this problem, we have to include the negative divisors of $P$ in our calculation. For example, $4$ will have the following divisors $(1,2,4,-1,-2,-4)$.
Example
Find solutions for $2xy + 2x + 2y = 4$.
First we will find $P = AD + BC = 2 \times 4 + 2 \times 2 = 12$. $12$ has the following divisors: $(\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 12 )$.
Since $(2x + 2)(2y + 2 ) = 12$, we get the following:
$d_1 = 1: x = \frac{1-2}{2} = \frac{-1}{2}, y = \frac{12 – 2 \times 1}{2 \times 1} = \frac{10}{2} = 5$
$d_2 = -1: x = \frac{-1-2}{2} = \frac{-3}{2}, y = \frac{12 – 2 \times -1}{2 \times -1} = \frac{14}{-2} = -7$
$d_3 = 2: x = \frac{2-2}{2} = 0, y = \frac{12 – 2 \times 2}{2 \times 2} = \frac{8}{4} = 2$
$d_4 = -2: x = \frac{-2-2}{2} = -2, y = \frac{12 – 2 \times -2}{2 \times -2} = \frac{16}{-4} = -4$
$d_5 = 3: x = \frac{3-2}{2} = \frac{1}{2}, y = \frac{12 – 2 \times 3}{2 \times 3} = \frac{6}{6} = 1$
$d_6 = -3: x = \frac{-3-2}{2} = \frac{-5}{2}, y = \frac{12 – 2 \times -3}{2 \times -3} = \frac{18}{-1} = -18$
$d_7 = 4: x = \frac{4-2}{2} = 1, y = \frac{12 – 2 \times 4}{2 \times 4} = \frac{4}{8} = \frac{1}{2}$
$d_8 = -4: x = \frac{-4-2}{2} = -3, y = \frac{12 – 2 \times -4}{2 \times -4} = \frac{20}{-8} = \frac{-5}{2}$
$d_9 = 6: x = \frac{6-2}{2} = 2, y = \frac{12 – 2 \times 6}{2 \times 6} = \frac{0}{12} = 0$
$d_{10} = -6: x = \frac{-6-2}{2} = -4, y = \frac{12 – 2 \times -6}{2 \times -6} = \frac{24}{-12} = -2$
$d_{11} = 12: x = \frac{12-2}{2} = 5, y = \frac{12 – 2 \times 12 }{2 \times 12 } = \frac{-12}{24} = \frac{-1}{2}$
$d_{12} = -12: x = \frac{-12-2}{2} = -7, y = \frac{12 – 2 \times -12 }{2 \times -12 } = \frac{36}{-24} = \frac{-3}{2}$
So the solutions are $(0,2),(-2,-4),(2,0),(-4,-2)$.
Code
Let us try to write a function that will count the number of solutions for the given problem above. If there are infinite solutions, the function will return $-1$.
bool isValidSolution ( int a, int b, int c, int p, int div ) {
if ( ( ( div - c )% a ) != 0 ) return false; //x = (div - c) / a
if ( ( (p-b*div) % (a*div) ) != 0 ) return false;// y = (p-b*div) /(a*div)
return true;
}
int hyperbolicDiophantine ( int a, int b, int c, int d ) {
int p = a * d + b * c;
if ( p == 0 ) { //ad + bc = 0
if ( -c % a == 0 ) return -1; //Infinite solutions (-c/a, k)
else if ( -b % a == 0 ) return -1; //Infinite solutions (k, -b/a)
else return 0; //No solution
}
else {
int res = 0;
//For each divisor of p
int sqrtn = sqrt ( p ), div;
for ( int i = 1; i <= sqrtn; i++ ) {
if ( p % i == 0 ) { //i is a divisor
//Check if divisors i,-i,p/i,-p/i produces valid solutions
if ( isValidSolution(a,b,c,p,i) )res++;
if ( isValidSolution(a,b,c,p,-i) )res++;
if ( p / i != i ) { //Check whether p/i is different divisor than i
if ( isValidSolution(a,b,c,p,p/i) )res++;
if ( isValidSolution(a,b,c,p,-p/i) )res++;
}
}
}
return res;
}
}
We have two functions here. The first function $\text{isValidSolution}()$ takes input $a,b,c, p, div$ and checks whether we can get a valid solution $(x,y)$ using $div$ as a divisor of $P$.
In line $7$ we start our function to find number of solutions. In line $10$ We check our first case when $AD + BC = 0$. If it is possible to form a valid solution, we return $-1$ in line $11,12$ otherwise $0$ in line $13$.
From line $15$ we start case when $AD + BC \neq 0$. For this case we have to find all divisors of $P$. We know that all divisors come in pairs and one part of that pair lies before $\sqrt{P}$. We we loop till $\sqrt{P}$ to find first part of the pair and process it in line $16$. The second part can be found by dividing $P$ by the first part. We process both these parts ( if second part is different than first part, line $26$ ) and their negative parts by passing them to $\text{isValidSolution}()$ functions. If they are valid we increase our result by 1.
If we are asked to print the solutions, we could do it by modifying the functions above. As long as we understand how the solution works, there should not be any problem in modifying the functions.