Show that there are infinitely many positive integer numbers $n$ such that $n^2+1$ has two positive divisors whose difference is $n$.
Problem
Source: Romania BMO/IMO TST 2011 P12.
Tags: number theory unsolved, number theory
29.01.2012 20:47
Define a sequence $(a_k)_{k\geq 0}$ by $a_0=1$, $a_1=2$, and $a_{k+2}a_k = a_{k+1}^2 + 1$ for $k\geq 0$. Then $a_2 = 5$. Writing $a_{k+2}a_k = a_{k+1}^2 + 1$ and $a_{k+1}a_{k-1} = a_{k}^2 + 1$ for $k\geq 1$, and subtracting the two, we get $(a_{k+2} + a_k)a_k = (a_{k+1} + a_{k-1})a_{k+1}$. Since the terms are clearly not-null, we can write this as $\frac {a_{k+2} + a_{k}} {a_{k+1}} = \frac {a_{k+1} + a_{k-1}} {a_{k}} = \cdots = \frac {a_{2} + a_{0}} {a_{1}} = 3$, so the sequence satisfies the second order linear recurrence $a_{k+2} = 3a_{k+1} - a_k$, so all terms are positive integers. Then $n_k = a_{k+1} - a_k$, $k\geq 0$, is obviously an increasing sequence of positive integers, and $a_{k+1}$, $a_k$ both divide $n_k^2 + 1 = (a_{k+1} - a_k)^2 + 1 =$ $ (a_{k+1}^2 + 1) + a_k^2 - 2a_ka_{k+1} =$ $ a_k(a_{k+2} + a_k) - 2a_ka_{k+1} =$ $ 3a_ka_{k+1} - 2a_ka_{k+1} = a_ka_{k+1}$.
29.01.2012 20:49
Let $\left \{ x_n \right \} , \left \{ y_n \right \}$ be the sequence of solution to below Pell equation : ${y_n}^2 - 5 {x_n}^2 =4$ ($x_1 =1 , y_1 =3$) Then ${x_n}^2 +1 = (\frac{x_n + y_n}{2})(\frac{y_n - x_n}{2})$ , note that $(\frac{x_n + y_n}{2}) - (\frac{y_n - x_n}{2}) = x_n$
04.02.2012 16:01
As well know $Fibonacci$ sequence: ${u_1} = 1, {u_2} = 1, {u_{n + 2}} = {u_n} + {u_{n + 1}},n \geqslant 1$ satisfies $u_{n + 1}^2 - {u_{n + 2}}{u_n} = {( - 1)^n}$, so $u_{2k}^2 + 1 = {u_{2k + 1}}{u_{2k - 1}}$, and ${u_{2k + 1}} - {u_{2k - 1}} = {u_{2k}}$, hence we can take $n = {u_{2k}}$.
18.08.2013 19:31
if we show that there are infinitely many natural number solutions to $n^2+1=d(n+d)$ , then we are done. this equation is equivalent to $n^2-dn+1-d^2=0$......(*). now its discriminant $\Delta =5d^2-4$ now , $5d^2-4=y^2$ has infinitely many solutions in natural numbers with initial solution $(1,1)$. hence , (*) has infinitely many solutions and we are done
22.09.2015 08:50
A nice one... Let $n=2m$ and Let $(t,m)$ satisfy the Pell's Equation $t^2-5m^2=1$ Then Put $d=t-m$ and observe that $\frac{n^2+1}{t-m} -(t-m)=\frac{t^2-m^2}{t-m}-(t-m)=2m$ and so since this Pell type Equation has infinitely many solutions we are done.
11.08.2017 13:34
mathbuzz wrote: if we show that there are infinitely many natural number solutions to $n^2+1=d(n+d)$ , then we are done. this equation is equivalent to $n^2-dn+1-d^2=0$......(*). now its discriminant $\Delta =5d^2-4$ now , $5d^2-4=y^2$ has infinitely many solutions in natural numbers with initial solution $(1,1)$. hence , (*) has infinitely many solutions and we are done But i rhink u also have to show that $d + sqrt( 5d^2 - 4)$ is an even number to get n as an Integer.
12.09.2018 13:46
My solution:(vieta jumping):First note that the condition is equal to find infinity pairs of $n,m$ such that $m(m+n)|n^2+1$ now let $m+n=t$ the divisibility is equel to $mt|m^2+t^2+1$ which is well known that $3mt=m^2+t^2+1$has infinity many solutions. Remark:This solution also shows that if $n^2+1$ has two divisors with difference $n$ then $n^2+1$ is the multiply of that two divisors.
13.09.2018 09:07
Shortest solution not relying on other facts. Suppose we have $n^2+1=\tfrac{m^2-n^2}4$ for some odd positive $n$ and $m$, then $n^2+1=\left(\tfrac{m-n}2\right)\!\left(\tfrac{m+n}2\right)$. Now take $(n,m)=(1,3)$ as the initial pair and successively use the transform $(n,m) \mapsto (nm,m^2-2)$ with the fact $$n^2+1=\frac{m^2-n^2}4 \implies n^2m^2+m^2=\frac {m^4-n^2m^2}4 \implies (nm)^2+1=\frac{(m^2-2)^2-(nm)^2}4.$$
08.07.2019 12:37
We call a pair $(n,a)$ good if $a^2+an =n^2+1$ and $a$ is positive. Then also $(2n+a, n+a)$ is good because $$(n+a) (3n+2a) = 3n^2 + 5an + 2a^2 = 3n^2 + 4an + a^2 + n^2 + 1 = (2n+a)^2 + 1$$Since the left term from the pair is increasing and $(3,2)$ is good, the conclusion follows.
21.02.2021 15:32
(f_2n)^2+1=(f_2n-1)*(f_2n+1),f_n is Fibonacci sequence.
02.02.2023 01:26
This solution finds all the solutions, it does not only prove the existence of infinitely many.