I'm dealing with special kind of "Diophantine Equation". I want to generate all the solutions for
$x^2 - aby^2 = a^2 - ab$
given $a,b \in \mathbb{N} $, $a > b$, $a$ and $b$ are co-primes
I can easily generate a solution for this problem by putting $x = a, y = 1$
Since, $gcd(a,1)=1$, this is also a "primitive solution"
Now, I want to generate all the solutions with $x,y \in \mathbb{N}$. How to generate other solutions?
It'll be helpful if someone can tell me via recurrence. something like
$X_{n+1} = p.X_n + q.Y_n + k $
$Y_{n+1} = r.X_n + s.Y_n + l $
Edit: Thanks to André Nicolas I know how to generate all solution from the primitive solution.
@MISC {228390, TITLE = {How to find solutions of $x^2-3y^2=-2$?}, AUTHOR = {André Nicolas (https://math.stackexchange.com/users/6312/andr%c3%a9-nicolas)}, HOWPUBLISHED = {Mathematics Stack Exchange}, NOTE = {URL:https://math.stackexchange.com/q/228390 (version: 2012-11-03)}, EPRINT = {https://math.stackexchange.com/q/228390}, URL = {https://math.stackexchange.com/q/228390} }
But, I'm still missing on the "primitive solutions". Apparently, sometimes there are more than 1 primitive solutions. But I don't know how to find other "primitive solutions"?
Edit2:
I actually found a way to solve these type of equations. http://www.jpr2718.org/FundSoln.pdf
But it requires finding $z^2 \equiv a.b \: (\mathbb{mod} \, a(a-b))$ (Quadratic residue). Which I don't know how to compute efficiently. (Tonelli and other algorithms only works for prime).
My thoughts
Rearranging $x^2 - aby^2 = a^2 - ab$ gives $$x^2 - a^2 = ab \left( y^2 - 1 \right) $$
$a$ must be a divisor of either $x+a$ or $x-a$, therefore $a$ must be a divisor of $x$. Therefore let $x=na$, giving $$a(n^2-1)=b(y^2-1)$$
$a$ and $b$ only need compensate for prime factors not common to both $(n^2-1)$ and $(y^2-1)$, which means co-prime $a$ and $b$ can be chosen for any values of $n$ and $y$ with $y>n$.