0
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ since, $a$ and $b$ are co-primes we can conclude $n^2-1 = kb$ and $y^2-1=ka$ for some $k \in \mathbb{N}$ . I tried over iterating n for finding k. But i'm getting timeout on large a,b. Is there any other method? $\endgroup$ – Rahul Sharma Sep 7 '17 at 1:29
  • $\begingroup$ Choose $y$. There will be a solution for every positive $n$, $ (n< y)$. For a particular $n$, $k=gcd(y^2-1,n^2-1)$. Once $k$ is determined $a$, $b$ and $x$ can be found. $\endgroup$ – James Arathoon Sep 7 '17 at 15:22
  • $\begingroup$ $a$ and $b$ is given, we need to find $n$ and $y$. I understood the gcd part. Can you please explain how to generate the solutions? $\endgroup$ – Rahul Sharma Sep 7 '17 at 17:52
  • $\begingroup$ Sorry I missed the fact that $a$ and $b$ are given. If you calculate $\frac{y^2-n^2}{a-b}-\frac{y^2+n^2-2}{a+b}$ on a spreadsheet by varying $y$ and $n$ (e.g. with $a=12$ $b=5$) you get a surface that passes though the zero plane. I don't think there is a quick way to locate integer co-ordinates that give zero, along the line of intersection with the zero plane (that is at $y=17$, $n=11$) $\endgroup$ – James Arathoon Sep 7 '17 at 20:30
  • $\begingroup$ I actually found a way to solve these type of equations, 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. jpr2718.org/FundSoln.pdf $\endgroup$ – Rahul Sharma Sep 7 '17 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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