1

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.

Thanks

devoured elysium
  • 259

1 Answers1

4

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

Thomas Andrews
  • 177,126