Integer points on a hyperbola
Why I'm here
I have the following problem in probability from a book:
You have a bag with red and white balls and you draw two balls without replacing. If the probability of drawing 2 white balls is exactly 50%, how many balls are in the bag?
Suppose x is the number of red balls and y is the number of white balls. I can figure out the smallest solutions by trying out small numbers: $(1,3)$ and $(6,15)$. But are there any others?
My Work
The probability of getting two white balls (call that e) is
$\mathbb{P}(e)=\frac{1}{2}=\frac{y}{x+y}\cdot\frac{y-1}{x+y-1}$
Which gives me this quadratic equation:
$x^2+2xy-y^2-x+y=0$
And any positive integer points on this curve should be solutions to the problem. All I need to do is to find the integer points.
First I had the idea that if I draw a line with rational slope from the first point, I should reach a second rational point in the hyperbola. If I connect the two points I found, I get a line with equation $y=12/5(x-1)+3$, and because there are no integer solutions between (1,3) and (6,15), I want a line with higher slope. On the other hand, I can tell that the hyperbola has an asymptote $y=(1+\sqrt2)x+1/2$, so I want a line with a slope below $1+\sqrt2$, or the second intersection will be in the wrong branch of the hyperbola.
I had a vague idea that continued fractions help with diophantine equations, so I decided to try using the convergents of $1+\sqrt2$ to get my rational points. They're guaranteed to be above $12/5$ and exactly half of them will be below $1+\sqrt2$, so it's worth a try. These are the points I came up with:
(only every other slope will give a positive point)
slope | x | y |
-----------+--------+--------+
1+5/7 | 6 | 15 |
1+12/17 | -35 | -84 |
1+29/41 | 204 | 493 |
1+70/99 | -1189 | -2870 |
1+169/239 | 6930 | 16731 |
1+408/577 | -40391 | -97512 |
1+985/1393 | 235416 | 568345 |
And here is a surprise: all the numbers so far are integers! They all also satisfy the initial question, and every other convergent of $\sqrt2$ is giving me a new solution to the problem. I have tried other lines with rational slopes (by averaging the slopes of two consecutive solutions) but so far, I can't find any other integer solution.
My Question
Are all (sub-) convergents of $\sqrt2$ going to give me an integer point in the positive part of the hyperbola? Are there any other integer points in the positive part of the hyperbola?
I know that the general quadratic equation in integers was solved by Lagrange, but this method seems really different from what I'm doing here, it only uses the continued fraction to find the first solution (so not all convergents produce a solution), and then produces a recursive function for the rest of them. Is there any relation here?
Also, if you'd be so kind, could you suggest some expository material around quadratic equations in integers?
Other Stack Exchange questions
The following questions have been helpful to me so far:
- How to solve inhomogeneous quadratic forms in integers?
- Convergents as solutions for Pell's equation
Added: a careful proof that all solutions arise in the way described below begins with the observation that a solution $(x,y),$ with $|x|+|y|$ large, has either $x \approx (\sqrt 2 - 1) y$ or $y \approx (1-\sqrt 2)x.$ In the first case, we find $(2x-y) \approx -(3 - \sqrt 8) y.$ In the second case, $x+2y \approx (3 - \sqrt 8) x.$ Note that $(3 - \sqrt 8) \approx 0.17.$ That is, any solution can be moved until, say, $|x|+|y| \leq 10$ and all solutions in that diamond can be found.
The method for linking up all integer solutions is usually called Vieta Jumping on this site. In the infamous contest questions where this was first used, the quadratic form was of the type $x^2 - kxy + y^2.$ As it happens, there is no difficulty working the same technique when the quadratic part is $x^2 \pm kxy - y^2.$ This is a special case of the automorphism group of a (binary) quadratic form. As the coefficients of $x^2$ and $y^2$ both have absolute value $1,$ it becomes unnecessary to complete any squares or explicitly consider any Pell equations. The curious might borrow Binary Quadratic Forms by Buchmann and Vollmer. My favorite is Binary Quadratic Forms by Duncan A. Buell.
All the integer points can be produced by alternating two mappings beginning at the origin. The result is a double spiral, counterclockwise going outward, or clockwise going inward back to the origin.
Given an integer point on the spiral $(x,y),$ the neighboring spiral point with the same $x$ value, joined by a vertical line segment, is $$ (x, 1+2x-y) $$
Given an integer point $(x,y),$ the neighboring spiral point with the same $y$ value, joined by a horizontal line segment, is $$ (1-x-2y, y) $$
If you use on of these mapping twice in a row, you go back to where you started; this is why we alternate.
int x,y;
x = 1189; y = 2871;
cout << " $$ ( " << x << ", " << y << " ) $$ " << endl;
while ( abs(x) < 10000 && abs(y) < 10000)
{
y = 1 + 2 * x - y;
cout << " $$ ( " << x << ", " << y << " ) $$ " << endl;
x = 1 - x - 2 * y;
cout << " $$ ( " << x << ", " << y << " ) $$ " << endl;
}
Note that this , well, path, moves in on one spiral arm then back out on the other; they really make up a single path.
$$ ( 1189, 2871 ) $$ $$ ( 1189, -492 ) $$ $$ ( -204, -492 ) $$ $$ ( -204, 85 ) $$ $$ ( 35, 85 ) $$ $$ ( 35, -14 ) $$ $$ ( -6, -14 ) $$ $$ ( -6, 3 ) $$ $$ ( 1, 3 ) $$ $$ ( 1, 0 ) $$ $$ ( 0, 0 ) $$ $$ ( 0, 1 ) $$ $$ ( -1, 1 ) $$ $$ ( -1, -2 ) $$ $$ ( 6, -2 ) $$ $$ ( 6, 15 ) $$ $$ ( -35, 15 ) $$ $$ ( -35, -84 ) $$ $$ ( 204, -84 ) $$ $$ ( 204, 493 ) $$ $$ ( -1189, 493 ) $$ $$ ( -1189, -2870 ) $$ $$ ( 6930, -2870 ) $$ $$ ( 6930, 16731 ) $$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Moving outward on the black spiral, which contains (1,3)
mpz_class x,y;
x = 1; y = 0;
cout << " $$ ( " << x << ", " << y << " ) $$ " << endl;
while ( abs(x) < 2000000000 && abs(y) < 2000000000)
{
y = 1 + 2 * x - y;
cout << " $$ ( " << x << ", " << y << " ) $$ " << endl;
x = 1 - x - 2 * y;
cout << " $$ ( " << x << ", " << y << " ) $$ " << endl;
}
$$ ( 1, 0 ) $$ $$ ( 1, 3 ) $$ $$ ( -6, 3 ) $$ $$ ( -6, -14 ) $$ $$ ( 35, -14 ) $$ $$ ( 35, 85 ) $$ $$ ( -204, 85 ) $$ $$ ( -204, -492 ) $$ $$ ( 1189, -492 ) $$ $$ ( 1189, 2871 ) $$ $$ ( -6930, 2871 ) $$ $$ ( -6930, -16730 ) $$ $$ ( 40391, -16730 ) $$ $$ ( 40391, 97513 ) $$ $$ ( -235416, 97513 ) $$ $$ ( -235416, -568344 ) $$ $$ ( 1372105, -568344 ) $$ $$ ( 1372105, 3312555 ) $$ $$ ( -7997214, 3312555 ) $$ $$ ( -7997214, -19306982 ) $$ $$ ( 46611179, -19306982 ) $$ $$ ( 46611179, 112529341 ) $$ $$ ( -271669860, 112529341 ) $$ $$ ( -271669860, -655869060 ) $$ $$ ( 1583407981, -655869060 ) $$ $$ ( 1583407981, 3822685023 ) $$ $$ ( -9228778026, 3822685023 ) $$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Moving outward on the purple spiral, which contains (6,15)
mpz_class x,y;
x = 0; y = 0;
cout << " $$ ( " << x << ", " << y << " ) $$ " << endl;
while ( abs(x) < 2000000000 && abs(y) < 2000000000)
{
y = 1 + 2 * x - y;
cout << " $$ ( " << x << ", " << y << " ) $$ " << endl;
x = 1 - x - 2 * y;
cout << " $$ ( " << x << ", " << y << " ) $$ " << endl;
}
$$ ( 0, 0 ) $$ $$ ( 0, 1 ) $$ $$ ( -1, 1 ) $$ $$ ( -1, -2 ) $$ $$ ( 6, -2 ) $$ $$ ( 6, 15 ) $$ $$ ( -35, 15 ) $$ $$ ( -35, -84 ) $$ $$ ( 204, -84 ) $$ $$ ( 204, 493 ) $$ $$ ( -1189, 493 ) $$ $$ ( -1189, -2870 ) $$ $$ ( 6930, -2870 ) $$ $$ ( 6930, 16731 ) $$ $$ ( -40391, 16731 ) $$ $$ ( -40391, -97512 ) $$ $$ ( 235416, -97512 ) $$ $$ ( 235416, 568345 ) $$ $$ ( -1372105, 568345 ) $$ $$ ( -1372105, -3312554 ) $$ $$ ( 7997214, -3312554 ) $$ $$ ( 7997214, 19306983 ) $$ $$ ( -46611179, 19306983 ) $$ $$ ( -46611179, -112529340 ) $$ $$ ( 271669860, -112529340 ) $$ $$ ( 271669860, 655869061 ) $$ $$ ( -1583407981, 655869061 ) $$ $$ ( -1583407981, -3822685022 ) $$ $$ ( 9228778026, -3822685022 ) $$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
I know that the general quadratic equation in integers was solved by Lagrange, but this method seems really different from what I'm doing here, it only uses the continued fraction to find the first solution (so not all convergents produce a solution), and then produces a recursive function for the rest of them.
I like Dario Alpern's online calculator.
Enter the coefficients and push "show steps". It gives a nice explanation about how it solves the equation.
It seems to be the cited method:
$x^2 + 2 xy - y^2 - x + y = 0$
The discriminant is $b^2− 4ac = 8$
Let $D$ be the discriminant. We apply the transformation of Legendre $Dx = X + \alpha$, $Dy = Y + \beta$, and we obtain:
$\alpha = 2cd - be = 0$
$\beta = 2ae - bd = 4$
$X^2 + 2 XY - 1 = -16 \quad (1)$
where the right hand side equals $−D (ae^2− bed + ed^2 + fD)$
We will have to solve several quadratic modular equations. To do this we have to factor the modulus and find the solution modulo the powers of the prime factors. Then we combine them by using the Chinese Remainder Theorem.
The different moduli are divisors of the right hand side, so we only have to factor it once.
$-16 = −2^4$
Searching for solutions $X$ and $Y$ coprime.
We have to solve: $T^2 + 2 T - 1 \equiv 0 \pmod {-16 = −2^4}$
There are no solutions modulo $2^4$, so the modular equation does not have any solution.
Let $X' = 2X$ and $Y' = 2Y$. Searching for solutions $X’$ and $Y'$ coprime.
From equation $(1)$ we obtain $X'^2 + 2 X'Y' - 1 = -16 / 2^2 = -4$
We have to solve: $T^2 + 2 T - 1 \equiv 0 \pmod{-4 = −2^2}$
There are no solutions modulo $2^2$, so the modular equation does not have any solution.
Let $X' = 4X$ and $Y' = 4Y$. Searching for solutions $X'$ and $Y'$ coprime.
From equation $(1)$ we obtain $X'^2 + 2 X'Y' - 1 = -16 / 4^2 = -1$
We have to solve: $T^2 + 2 T - 1 \equiv 0 \pmod{ -1 = −1}$
$T = 0$
The transformation $X' = k \quad (2)$ converts $X'^2 + 2 X'Y' - 1 = -1$ to $PY'^2 + QY'k + R k^2 = 1\quad (3)$ where: $P = (aT^2 + bT + c) / n = 1$, $Q = −(2aT + b) = -2$, $R = an = -1$
The continued fraction expansion of $(Q + \sqrt{D / 4}) / R = (-1 +\sqrt{ 2}) / 1$ is:
$0+ // 2// \quad (4)$Solution of $(3)$ found using the convergent $Y' / (−k) = 1 / 0$ of $(4)$
From $(2)$: $X' = 0$, $Y' = 1$
$X = 0$, $Y = 4$
$X + \alpha = 0$, $Y + \beta = 8$
Dividing these numbers by $D = 8$:
$x = 0$
$y = 1$$X = 0$, $Y = -4$
$X + \alpha= 0$, $Y + \beta = 0$
Dividing these numbers by $D = 8$:
$x = 0$
$y = 0$The continued fraction expansion of $(−Q +\sqrt{ D / 4}) / (−R) = (1 + \sqrt{2}) / (-1)$ is: $-3+ // 1, 1, 2// \quad (5)$
Solution of $(3)$ found using the convergent $Y' / (−k) = 1 / -2$ of $(5)$
From $(2)$: $X' = -2$, $Y' = 1$
$X = -8$, $Y = 4$
$X + \alpha = -8$, $Y + \beta = 8$
Dividing these numbers by $D = 8$:
$x = -1$
$y = 1$$X = 8$, $Y = -4$
$X + \alpha = 8$, $Y + \beta = 0$
Dividing these numbers by $D = 8$:
$x = 1$
$y = 0$$\fbox{$\fbox{$x = 0 \\ y = 1$}$}$
$\fbox{$\fbox{$x = 0 \\ y = 0$}$}$
Recursive solutions:
$x_{n+1} = x_n + 2 y_n - 1\\y_{n+1} = 2 x_n + 5 y_n - 2$
and also:
$x_{n+1} = 5 x_n - 2 y_n + 1\\y_{n+1} = - 2 x_n + y_n$
Written by Dario Alpern. Last updated on 25 July 2018.