To prove a divisor to be a perfect square

Let $m$ and $n$ be positive integers, where $m$ is bigger than $n$ and $m+n$ is even. If $m^2-n^2+1\mid n^2-1$, prove that $m^2-n^2+1$ is a perfect square.

I don't really have some valuable clues or ideas about the problem. May be Method of infinite descent can be applied here, but who knows. We can turn the problem into a diophantine equation whose $LHS$ and $RHS$ and be factorized, but I can't proceed any more.

When $m<300$, there are 3 solutions $(m,n) = (30,26), (105,99), (252,244)$

Heard the problem is from a Russian math contest.

• It seems like a start to note that $m^2-n^2+1\mid n^2-1$ if and only if $m^2-n^2+1\mid (n^2-1)+(m^2-n^2+1)=m^2$. – Thomas Andrews Apr 8 '16 at 14:38
• @ThomasAndrews Right, I've tried, but failed to achieve anything.. – cxz Apr 8 '16 at 14:39
• If it's true and if there is an example, the evenness of m+n will be necessary, as m=10, n=9 (with m+n odd) would fail. – DanielWainfleet Apr 8 '16 at 14:53
• When you say "no answers can be found," you mean with $m^2-n^2+1$ not a square, right? – Thomas Andrews Apr 8 '16 at 14:59
• I mean not any $(m,n)$ with $m>n$, $m+n$ even, and $m^2-n^2+1|n^2-1$ is found. quite strange. – cxz Apr 8 '16 at 15:02

Write $m^2-n^2+1=cy^2$ where $c$ is square-free. Then $m^2=c^2y^2b^2$ for some $b$, and then you get the Pell equation:

$$n^2-(c^2b^2-c)y^2=1$$

You need to show that if $c>1$ is square-free, there is no solution to this Pell equation with $n,cby$ the same parity, which is the same as saying that $cy^2$ is odd. In particular, $c$ and $y$ must be odd.

This is where the magic happens:

$$4b^2(b^2c^2-c) = (2b^2c-1)^2-1.$$ So you just need to show that $(x,y)=(2b^2c-1,2b)$ is the elementary solution to $x^2-(b^2c^2-c)y^2=1$, which means there is no solution with $y$ odd.

It is not an elementary solutio when $c=1$ because then $(x,y)=(b,1)$ is the elementary solution.

The continued fraction for $\sqrt{b^2c^2-c}$ starts: $[bc-1,1,2b-2,1,2bc-2,\dots]$ with that yielding $y=2b$, and no prior continued fraction yields a solution, except again when $c=1$.

When $c=1$,the elementary solution $(x,y)=(b,1)$ indicates the general solution to the Pell equation is:

$$x+y\sqrt{b^2-1}=(b+\sqrt{b^2-1})^k$$

But if you know Chebyshev polynomials, this is:

$$x=T_k(b),y=U_{k-1}(b)$$

and $y$ is odd precisely when $k$ is odd, so you get:

$$(m,n)=(bU_{2k}(b),T_{2k+1}(b))$$ Is the general solution.

I was wondering if there was a way to avoid the Pell equation stuff. Maybe writing $p=(m+n)/2,q=(m-n)/2$ and thus $m=p+q,n=p-q$ yielding the condition:

$$4pq+1\mid (p+q)^2$$

Not sure how to proceed from there, but you need to show that then $4pq+1$ is a perfect square under this condition, and there is no longer a parity condition.

Writing $4pq+1=a^2c$ with $c$ square-free, and $p+q=abc$ for some $b$, the replace $q=abc-p$ and get: $4p(abc-p)=a^2c-1$ or $4p^2-4abcp + a^2c-1=0$, meaning that:

$$p=\frac{4abc\pm \sqrt{16a^2b^2c^2-16(a^2c-1)}}{8}=\frac{abc\pm \sqrt{a^2b^2c^2-a^2c+1}}{2}$$

So you need $a^2b^2c^2-a^2c+1$ to be a square of the same parity as $abc$, which just gets us back to the Pell equation and the parity condition.

So the Pell equation does seem to be the heart of it.