I have the fundamental solution of the following Diophantine equation: $$\frac{x(x-1)}{y(y-1)}=\frac{m}{n} \hspace{5 mm}, \hspace{5 mm} m \le n$$ $$nx^2-my^2-nx+my=0$$ Is it possible to derive a recurrence relation using which we can get the complete set of solution?

For example, if $m=1$ and $n=2$, then initial solution is $(x,y)=(3,4)$ and we can get the next solution by the linear transformation $(x,y) \rightarrow (3x+2y-2,4x+3y-3)$.

Can it be generalised for all $(m,n)$?

My approach:

Let the transform be $(x,y) \rightarrow (ax+by+c,px+qy+r)$, then substituting these in original equation and after some simplification,

$$(na^2-mp^2)x^2-(mq^2-nb^2)y^2-(an-pm+2prm-2acn)x+(2bcn-bn-2qrm+qm)y+(2abn-2pqm)xy+(nc^2-nc-mr^2-mr)=0$$ Comparing with original equation we have to solve following set of equations: $$na^2-mp^2=n$$ $$mq^2-nb^2=m$$ $$an-pm+2prm-2acn=n$$ $$2bcn-bn-2qrm+qm=m$$ $$2abn-2pqm=0$$ $$nc^2-nc-mr^2-mr=0$$ Is there any method using I can solve these equations efficiently to get $(a,b,c)$ and $(p,q,r)$?


Using the method http://www.alpertron.com.ar/METHODS.HTM, I have to solve $r^2-mns^2=1$ and find the fundamental solutions.

Let $X_n$ and $Y_n$ be the initial solution, then next solutions will be:

$$X_{n+1}=(r^2+mns^2)X_n+2mrsY_n-(mns^2+mrs)$$ $$Y_{n+1}=2nrsX_n+(r^2+mns^2)Y_n-(mns^2+nrs)$$

For $m=1$ and $n=2$, $r=3$ and $s=2$, $$X_{n+1}=17X_n+12Y_n-14$$ $$Y_{n+1}=24X_n+17Y_n-20$$

Which gives the solution $(x,y):(3,4) \rightarrow (85,120)$ instead of $(x,y):(3,4) \rightarrow (15,21)$. This recurrence does not give complete set of solutions.

  • $\begingroup$ I think your best bet is to punch this system into maple or sage or some other piece of software and see if you can get an answer $\endgroup$ – Jeff Strom Sep 1 '15 at 4:57
  • 1
    $\begingroup$ The answer is positive. You can see the method here or you can find the solution here $\endgroup$ – GAVD Sep 1 '15 at 5:01
  • $\begingroup$ I am trying to solve hackerrank.com/contests/projecteuler/challenges/euler100 I think it should be solvable using standard programming languages like C++ / JAVA / Python $\endgroup$ – guest123456 Sep 1 '15 at 5:01
  • $\begingroup$ Thanks @GAVD for the link :) . The method is so much complicated. Anyway I should be able to implement the idea. It will require quite some time. $\endgroup$ – guest123456 Sep 1 '15 at 5:07
  • $\begingroup$ It is not clear. What else could be the issue? You also clearly shown that such an equation always can be associated with the Pell equation. math.stackexchange.com/questions/1414779/… Solutions of Pell equations standard procedure requiring the continued fraction decomposition. To abandon Pell equations fail. $\endgroup$ – individ Sep 1 '15 at 5:35

The condition can also be written as $$\iff n(x-\tfrac12)^2-m(y-\tfrac12)^2=\frac{m+n}4$$ $$\iff (2nx-n)^2-mn(2y-1)^2=n(m+n)$$ So with the substitution $u=n(2x-1), v = 2y-1$, we are looking for solutions to the Pell type equation $u^2-(mn)v^2=n(m+n)$, which allows recursive solutions (if you have any particular solution) depending on the value of $mn$.


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.