1
$\begingroup$

We need to find the smallest integral value of $x$ such that $2x^2-2x+1=(2m+1)^2$ and $x \ge 10^{15}$.

$\endgroup$
4
  • $\begingroup$ Is $x$ an integer? What have you tried so far? $\endgroup$ Sep 22, 2016 at 15:53
  • $\begingroup$ Yes. I have tried to find expression for $x$ solving the quadratic. That imposes restriction on $odd$ such that $2*odd^2-1$ must be a square of an odd number. $\endgroup$
    – maverick
    Sep 22, 2016 at 15:55
  • $\begingroup$ What about $x=0$? $\endgroup$
    – Paul
    Sep 22, 2016 at 15:59
  • $\begingroup$ Is $0 \ge 10^{15}?$ $\endgroup$
    – maverick
    Sep 22, 2016 at 16:02

3 Answers 3

4
$\begingroup$

HINT: $$2x^2 - 2x + 1 = (2m+1)^2 \iff x^2 + (x-1)^2 = (2m+1)^2$$

So the problem reduces to finding a specific Pythagorean triplet.

UPDATE:

We have that this is a primitive Pythagorean triplet, as $(x,x-1) = 1$. Therefore we either have $x = m^2 - n^2, x-1 = 2mn$ or $x=2mn, x-1 = m^2 - n^2$ for some positive integers $m,n$ which are coprime and one of them is odd.

Now going through the cases we have:

$$m^2-n^2 = 2mn+1 \iff (m-n)^2 = 2n^2 + 1$$

This is a Pell's Equation and has infinitely many solutions. So eventually you would be able to find a solution that will give you $x \ge 10^{15}$

Similarly for the other case we have:

$$m^2 - n^2 = 2mn - 1 \iff (m-n)^2 = 2n^2 - 1$$

Again this is a Pell's Equation, but this one is negative one, which doesn't change much.

$\endgroup$
2
  • $\begingroup$ That was one sharp observation. Is there some general technique to deal with such problems? $\endgroup$
    – maverick
    Sep 22, 2016 at 15:57
  • $\begingroup$ @maverick You can check the update I have posted in the answer $\endgroup$
    – Stefan4024
    Sep 22, 2016 at 16:12
1
$\begingroup$

According to Stefan4024, the solution for the Pythagorean triples are well-known:

$$\begin{pmatrix} x-1 \\ x \\ 2m+1 \end{pmatrix}= \begin{pmatrix} \frac{(\sqrt{2}+1)^{2k+1}-(\sqrt{2}-1)^{2k+1}}{4}-\frac{1}{2} \\ \frac{(\sqrt{2}+1)^{2k+1}-(\sqrt{2}-1)^{2k+1}}{4}+\frac{1}{2} \\ \frac{(\sqrt{2}+1)^{2k+1}+(\sqrt{2}-1)^{2k+1}}{2\sqrt{2}} \end{pmatrix}$$

Now $\dfrac{(\sqrt{2}+1)^{2k+1}}{4} \approx 10^{15} \implies 2k+1\gtrsim 40.76$

Put $2k+1=41$, then

$$\begin{pmatrix} x-1 \\ x \\ 2m+1 \end{pmatrix}= \begin{pmatrix} 1235216565974040 \\ 1235216565974041 \\ 1746860020068409 \end{pmatrix}$$

$\endgroup$
0
$\begingroup$

Thanks @Stefan4024 for the answer. However, on googling more, I found this site. This solves Quadratic Diophantine Equations of the type $$ a x^2 + b xy + c y^2 + dx + ey + f = 0$$ We need to provide values of coefficients $\{a,b,c,d,e,f\}$ and it gives us the output in recurrence form of the following type:
$$x_{n+1} = P x_n + Q y_n + K$$ $$y_{n+1} = R x_n + S y_n + L$$ where the coefficients $\{P,Q,R,S,K,L\}$ are also provided as an output. This is super awesome but I really don't know the mathematics behind it.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .