When working on a problem on Project Euler I came up with a formula I need to solve:

$N(N-1) = 2X(X-1)$ for $N > 10^{12}, X > 0$

with $N$ and $X$ being integer numbers.

After some investigation I came to the conclusion that this kind of problems is well known in mathematics, and that my equation is a so called Diophantine Equation.

Any pointers on how to proceed to solve this problem? I've read about Pell's Equation, but it doesn't seem to be a good fit for the aforementioned equation.



You can rewrite this equation as $$(2N-1)^2=2(2X-1)^2-1.$$ The Diophantine equation $u^2-2v^2=-1$ is well know.[*]

All the solutions to this equation have $u,v$ odd and are of the form $u+v\sqrt{2}=(1+\sqrt{2})^{2k+1}$. For example, $k=7$ gives:

$$(1+\sqrt{2})^{15} = 275807+195025 \sqrt{2}$$

So $N=137904$ and $X=97513$.

To get $N>10^{12}$, you need $k\geq 16$. I found that value by trial and error. The smallest is: $N=1070379110497$ and $X=756872327473$.

[*] This is called the Negative Pell Equation for $2$.


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.