Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

It suffices to find $c_n,d_n$ s.t. $a_n|c_n^2+1,\ a_n+1|d_n^2+1$, because then, since $(a_n,a_n+1)=1$, we can find $b_n\equiv c_n\pmod {a_n},\ b_n\equiv d_n\pmod{a_n+1}$. Let's show that $a_n=5^{2n}$ works. We have $a_n+1=5^{2n}+1=(5^n)^2+1$, so all we need to show is that there is some $c_n$ s.t. $5^{2n}|c_n^2+1$. We can show something more general: if $p$ is a prime of the form $4k+1$, then there is a $t_n$ s.t. $p^n|t_n^2+1$. We construct $t_n$ inductively. $t_1$ clearly exists, and assuming that $p^{n-1}|t_{n-1}^2+1$ we have to find $k\in\overline{0,p-1}$ s.t. $p^n|(t_{n-1}+kp^{n-1})^2+1$. This is reduced to $p|\frac{t_{n-1}^2+1}{p^{n-1}}+2k$, and it's clear that we can find such a $k$.

OFFICIAL SOLUTIONS Solution 1: Lemma: If $a,c \in \mathbb{N}$ and $a^{2}|c^{2}+1$ then there exists $b \in \mathbb{N}$ such that $a^{2}(a^{2}+1)|b^{2}+1$. Proof: Indeed $a^{2}|(c+a^{2}c-a^{3})^{2}+1$ and $a^{2} + 1|(c+a^{2}c-a^{3})^{2}+1$, so we can take $b=c+a^{2}c-a^{3}$. Using the lemma we see that it is enough to find strictly increasing sequences $(a_{n})$ and $(c_{n})$ such $a^{2}_{n}|c^{2}_{n}+1$ for every $n \in \mathbb{N}$. This can be realized by taking for instance $a_{n}=2^{2n}+1,c_{n}=2^{na_{n}}$. In this case \[ c^{2}_{n}+1=(2^{2n})^{a_{n}}+1=(a_{n}-1)^{a_{n}} \] is divisible by $a^{2}_{n}$. Solution 2: We will use factorizations over the ring $\mathbb{Z}[i]$. Take $(p,q,r)$ a Pythagorean triple $p^{2}=q^{2}+r^{2}$ and $a=p^{2}$. Then \[ a(a+1)=(q^{2}+r^{2})(p^{2}+1)=(q+ri)(p+i)(q-ri)(p-i) \] must divide $(b+i)(b-i)$. Therefore we have to find a Gaussian integer x+iy such that \[ (q+ri)(p+i)(x+yi)=b+i \] that is we have to find integers $x,y$ such that \[ (pr+q)x+(pq-r)y=1 \] It is easy to see that if $p,q,r$ are coprime then $pr+q$ and $pq-r$ are also coprime: if $d$ is a prime divisor of $pr+q$ and $pq-r$, then \[ d|q(pr+q)-r(pq-r)=q^{2}+r^{2}=p^{2}, \] hence $d|q$, which implies $d=1$. Thus the existence of $x,y$ is proven. The construction of the sequences $(a_{n})$ and $(b_{n})$ is now obvious.

Observe that since $b_n + (a_n)(a_n+1)$ works in lieu of $b_n$, we just need to find infinitely many $a_n$ such that there exists a $b_n$ where $a_n * (a_n + 1) | (b_n)^2 + 1$ Sorry to revive, but say we need $p^k | b_{n}^2 + 1$. Assume that there is a solution to $p | b_{n}^2 + 1$ for $b_{n}$. (quadratic reciprocity gives that these primes are of the form $1 \pmod 4$. Then since $b_n \not \equiv 0 \pmod p$, Hensel's lemma lets us lift these powers. Hence, it remains to show that we can find infinitely many $a_n$ such that $a_n$ and $a_n + 1$ have no prime factors which are $3 \pmod 4$ and are not multiples of $4$. But this is easy; indeed, observe that numbers of the form $4a^2 + 1$ have this property. Then just take $(4a^2+1)^2$ and $(4a^2+1)^2+1$ for $a_n$, and use Chinese Remainder theorem for the rest.

Let $a_n$ =$(q_n)^2$ where $(q_n)_{n\ge 1}$ is an increasing sequence of primes congruent to 1 mod 4.Let $a_n+1$ =$(p_1)^{\alpha_1}....(p_t)^{\alpha_t}$. Choose $b_n$ congruent to $r_i$ modulo $(p_i)^{\alpha_i}$ such that $(p_i)^{\alpha_i}$ divides $(r_i)^2 +1$ for $i$ equals $1,2,...,t$. also let $b_n$ congruent to $R_n$ modulo $(q_n)^2$ such that $(q_n)^2$ divides $(R_n)^2 +1$. Clearly by Hensel's Lemma such a construction is possible and such a $b_n$ exists by Chinese Remainder Theorem.Hence we found such sequences.(We can make $b_n$ strictly increasing quite easily)

Consider Pell-type equation $x^2-5y^2=-9.$ Take $x_i=2b_i$ and $y_i=2a_i+1$ and the rest follows.

My solution (along with some motivations): Note that it suffices to show that there exist two increasing sequences $x_n$ and $y_n$ such that $x_n^2 \equiv -1 \pmod{a_n}$ and $y_n^2 \equiv -1 \pmod{a_n+1}$, cause then, we can take the sequence $b_n$ with $b_n \equiv x_n \pmod{a_n}$ and $b_n \equiv y_n \pmod{a_n+1}$ (The existence of such a sequence $b_n$ is guaranteed by CRT). This works as $b_n^2 \equiv x_n^2 \equiv -1 \pmod{a_n}$ and $b_n^2 \equiv y_n^2 \equiv -1 \pmod{a_n+1}$, and so, using the fact that $\gcd(a_n,a_n+1)=1$, we get $b_n^2 \equiv -1 \pmod{a_n(a_n+1)}$. The fact that $a_n+1 \mid y_n^2+1$ inspires us to take $a_n=t_n^2$, for some increasing sequence $t_n$. Then taking $y_n=t_n$ works. Notice that the condition that the sequences are increasing is superfluous, as after finding the sequences, we can simply arrange them in increasing order. Renaming $t_n$ as $a$, our problem is reduced to the following- Remaining problem wrote: Show that there exist infinitely many positive integers $a$, such that $-1$ is a quadratic residue modulo $a^2$. Suppose $p$ is a prime divisor of $a$. Then $\left(\frac{-1}{p} \right)=1$, where the fraction denotes Legendre's symbol. Using Euler's criterion, we get $$1 \equiv \left(\frac{-1}{p} \right) \equiv (-1)^{\frac{p-1}{2}} \pmod{p} \Rightarrow p \equiv 1 \pmod{4}$$This motivates us to take $a=p$, such that $p \equiv 1 \pmod{4}$, which evidently gives that $-1$ is a quadratic residue modulo $a^2$. Hence, done. $\blacksquare$

One liner : One can show that the pair of sequences $a_n=(4n^2+1)^2, b_n=(8n^3+6n)+(4n^2+1)^2*(8n^3-4n^2+6n-1)$ works by polynomial division, hence this pair of sequence is one of the desired pairs, hence proved.

Note that $a_n= {y_n}^2$ where $y_n$ is the n-th solution to $x^2-2y^2=-1$ works

Not that hard for an N3, considering that I already did two other problems (off AoPS) about divisors of $n^2+1$ beforehand. From the problem, it is clear that for all $n$, we must have $$b_n^2=-1 \pmod {a_n(a_n+1)}.$$It is well-known by quadratic reciprocity that only $-1$ is only a quadratic residue modulo $2$ or any power of a prime $1$ modulo $4$. Therefore $a_n(a_n+1)$ must overall only contain factors of primes $1$ modulo $4$ and at most one factor of $2$. We claim that $a_n = p_n^2$, where $p_n$ is the $n$th prime equivalent to $1$ modulo $4$, follows the above condition. $a_n=p^2$ follows the conditions (and doesn't include a factor of $2$), while $a_n+1=p^2+1$ is itself one more than a square and therefore can only have factors of $1$ mod $4$ primes, with at most one factor of $2$, proving the claim. Considering every maximal prime power factor of $p_n^2(p_n^2+1)$, if $b_n$ is equal to a certain residue modulo that prime power, then that prime power will divide $b_n^2+1$. Therefore, by CRT, there will exist infinitely many $x$ so that $a_n(a_n+1)$ divides $x^2+1$. Therefore, we can make $b_n$ increasing, finishing the proof.

ISL marabot solve. Let $p_n$ denote the $n$th prime that is $1\pmod 4$ (there are infinitely many prime $1\pmod 4$ by Dirichlet's). Consider $a_n=p_n^2$. Then $a_n(a_n+1)=p_n^2(p_n^2+1)$. So $b_n^2\equiv -1\pmod {p_n^2(p_n^2+1)}$, so we need $b_n^2\equiv -1\pmod {p_n^2}$ and $b_n^2\equiv -1\pmod {p_n^2+1}$. Lemma: For any prime $q\equiv 1\pmod 4$, there exists a positive integer $s$ so that $q^2\mid s^2+1$ or in other words $s^2\equiv -1\pmod {q^2}$. Proof: Let $f(x)=x^2+1$. Then by the Law of Quadratic Reciprocity, there exists an $r$ so that $q|f(r)$. Now note that $f'(r)=2r\not\equiv 0\pmod q$, so by Hensel's Lemma, there is a positive integer $s$ so that $q^2|f(s)=s^2+1$. $\blacksquare$ Let $s$ be a residue $\pmod{p_n^2}$ so that $s^2\equiv -1\pmod{p_n^2}$. Consider $b_n\equiv s\pmod{p_n^2}$ and $b_n\equiv p_n\pmod{p_n^2+1}$. It's clear that this satisfies $b_n^2\equiv -1\pmod{a_n(a_n+1)}$. Note for any $n$, we can take $b_n$ to be arbitrarily large, larger than $b_{n-1}$, so we can construct the sequence $(b_n)$ that's strictly increasing.

Doesn't $a_n=n$ and $b_n=\sqrt{n^2+n-1}$ work? This solution feels to obvious to be right. Or do $a_n$ and $b_n$ have to be integers?

bump can anyone confirm or deny that my sequences work?

Note that we can always increase $b_n$ by $a_n(a_n+1)$ and $a_n(a_n+1)$ will still divide $b_n^2+1$. So, the condition that $(b_n)$ is increasing doesn't matter since it is always possible to make it increasing if it isn't. So, this problem is equivalent to showing that there's a strictly increasing sequence $(a_n)$ such that $-1$ is a quadratic residue modulo $a_n(a_n+1)$. This is equivalent to showing that for arbitrarily high integers $a$, $-1$ is a quadratic residue modulo $a$ and $a+1$. Assume towards a contradiction that there are a finite number of primes $p$ such that $-1$ is a quadratic residue modulo $p$. Let $p_1, p_2,\ldots, p_n$ be these primes. Then, let $q$ be a prime such that $q|(p_1p_2\cdots p_n)^2+1$. Then, $-1$ is a quadratic residue mod $q$, but $q$ is relatively prime to $p_1, p_2, \ldots, p_n$, a contradiction. So, there are infinitely many primes $p$ such that $-1$ is a quadratic residue mod $p$. Let $p$ be an odd prime such that $-1$ is a quadratic residue mod $p$. Then, there exists $a$ such that $a^2\equiv-1\pmod{p}$. Then, $$(a-2^{-1}a^{-1}(a^2+1))^2\equiv a^2+4^{-1}a^{-2}(a^2+1)^2-2\cdot a\cdot 2^{-1}a^{-1}(a^2+1)\equiv a^2-2\cdot a\cdot 2^{-1}a^{-1}(a^2+1)\equiv a^2-(a^2+1)\equiv -1\pmod p^2$$so $-1$ is a quadratic residue modulo $p^2$. Clearly, $-1$ is a quadratic residue modulo $p^2+1$. Since $p^2$ can be arbitrarily large, this completes the proof. Edit: @above I interpreted it as meaning integers but it never specifies that so technically your solution works

It comes down to finding infinitely many $a_n$ for which $-1$ is a quadratic residue mod both $a_n$ and $a_{n}+1.$ Call a number $n$ good if $-1$ is a quadratic residue mod $n$. If coprime $m,n$ are good then $mn$ is good. $~$ $1,2$ are good but no other powers of $2$ are. However, for primes $p>2,$ if $-1$ is a quadratic residue mod $p$, no new restrictions are added for higher powers of $p$ so $-1$ is a quadratic residue mod $p^2.$ $~$ Prime $p$ is good iff $\left(-1\right)^{\left(\frac{p-1}{2}\right)}\equiv 1\pmod n$ iff $p\equiv 1\pmod 4.$ We claim that $p^2$ and $p^2+1$ are both good. Clearly $p^2+1$ only contains one power of $2.$ $~$ $p^2$ being good is trivial, so let us show that if odd $q\mid p^2+1$ then $q\equiv 1\pmod 4.$ If $d$ is the order of $p$ mod $q$ then $d\mid 4$ but $d\neq 2$ which implies $d=4.$ However, $d\mid q-1$ so $q\equiv 1\pmod 4$ as desired.

Note that all we have to do is find some not necessarily increasing sequence $(b_n)$, as we can add $a_n(a_n+1)$ to $b_n$ allowing us to make it as big as possible. Thus the problem is equivalent to finding infinitely many $a$ for which $-1$ is a QR $\pmod{a}$ and $\pmod{a+1}$. We claim that any number $a$ with no $3 \pmod 4$ prime factor works. Since $a^2+1$ only has $1 \pmod 4$ prime factors, the following lemma will finish by CRT. Lemma: $-1$ is a QR $\pmod{p^n}$ for any prime $p \equiv 1 \pmod{4}$. Proof: We use induction on $n$. The base case is well known. For the inductive step, assume there exists $r^2 \equiv -1+mp^n \pmod{p^{n+1}}$. We then have that $$(p^n \frac{m}{2r} - r)^2 \equiv p^{2n} \frac{m^2}{4r^2} - m p^n + (-1+mp^n) \equiv -1 \pmod{p^{n+1}},$$so the lemma is proven and we are done.

@above i don't believe Quote: any number $a$ with no $3 \pmod 4$ prime factor works? take $a = 65$, then $a$ has only $1 \pmod{4}$ factors but we can clearly see that $-1$ is a NQR $\pmod{66}$... Consider the sequence of numbers $p_n$ that is defined to be the $n$th prime that is $1 \pmod{4}$ (by Dirichlet, infinitely many exist.) I claim $a_n = p_n^2$ works. For this it suffices to show that $-1$ is a quadratic residue $\pmod{p_n^2}$ and $\pmod{(p_n^2+1)}$, as then we define $b_n$ to be sufficiently large and satisfy $b^2_n \equiv -1 \pmod{p_n^2(p_n^2+1)}$. Claim: $-1$ is a quadratic residue $\mod p_n^2$. Proof. It is known that $-1$ is a quadratic residue $\mod p_n$ - now use Hensel's lemma to lift to $\mod p_n^2$. $\blacksquare$ Claim: $-1$ is a quadratic residue $\mod p_n^2 + 1$. Proof. It is well-known that $p_n^2 + 1$ has no factors that are $3 \pmod{4}$. For each odd prime factor of $p_n^2 + 1$, we may (using Hensel's lemma and the fact that $-1$ is a QR for all primes that are $1 \pmod{4}$) lift to a sufficient exponent of the prime factor. To finish, use CRT to stitch these prime factors together (and $2$, using that $-1 \equiv 1$ is a quadratic residue $\mod 2$) to obtain that $-1$ is a QR $\mod p_n^2+1$, as desired. $\blacksquare$ For the reasons mentioned above, we are done. $\square$

Edit: the solution is wrong since 4 isn’t square free. Will fix later. Apparently this stronger version that there are infinite $(a,b)$ such that $a^2+a = b^2+1$ is also true. Note that it suffices to prove there are infinite integer solutions to $a^2+a \mid b^2+1$ as we can just start with any $(a_1,b_1)$ and repeatedly choose $a_k>b_{k-1}$. It suffices to find infinitely many $(a,b)$ such that \[a^2+a = b^2+1 \iff a = \frac{-1 \pm \sqrt{4b^2+5}}{2}\]However, since there are infinite solutions to the Pell Equation $c^2-4b^2 = 5$ (since $(c,b) = (3,1)$ works), we can just take that value of $b$ to get \[a = \frac{c-1}{2}\]Since $c$ must be odd by the Pell Equation, $a$ is a positive integer, so there are infinitely many $(a,b)$ as desired.

The fact that $b$ is increasing is not really relevant, since we can just increase it by some multiple of $a_n(a_n+1)$ if it is not. Thus, the problem essentially asks us to prove that there are infinitely many $n$ for which $-1$ is a quadratic residue mod $n(n+1)$. We claim that $n=p^2$ for some prime $p\equiv1\pmod{4}$ works. We claim that $p^2(p^2+1)$ only has 1 mod 4 prime factors and 2, which would solve the problem. Suppose $q$ is an odd prime such that $q\mid p^2+1$. This means that $-1$ is a quadratic residue mod $q$, which means that $q$ is 1 mod 4. Thus, $p^2(p^2+1)$ only has 1 mod 4 prime factors, so $-1$ is a quadratic residue, done.

The problem basically forces the solution; it's just a matter of getting details to work.

by Chinese Remainder theorem. It follows that this sequence works.

The condition that $(b_n)$ is increasing doesn´t matter as we can always add a suficientely large factor of $a_n(a_n+1)$ to $b_n$. We claim that $-1$ is a quadratic residue $\pmod {p^2(p^2+1)}$, which is enough to finish; for a $p\equiv 1\pmod 4$ prime, it suffices to show that a prime divisor of $p^2(p^2+1)$ is $1\pmod 4$ which it´s true as $p^2$ has only $1\pmod 4$ prime factors as well as $p^2+1$

Consider an arbitrarily large solution $(x_n,y_n)$ to the equation $y_n^2=2x_n^2-1$. Choose $a_n=x_n^2$ and \[b_n\equiv y_n\pmod{x_n^2}\]\[b_n\equiv x_n\pmod{x_n^2+1}\]and we are done. $\blacksquare$

We consider the sequence $a_n=p_n^2$ where $p_n$ is the $n^{\text{th}}$ prime which is $1 \pmod{4}$. First, notice that due to Fermat's Christmas Theorem , we have that $a_n(a_n+1)=p_n^2(p_n^2+1)$ is composed of only primes which are $1 \pmod{4}$. We consider one such prime $p$. Then, we consider the function $f(x)=x^2+1 \pmod{p}$. Since all these primes $p \equiv 1 \pmod{4}$, by Legendre's definition we have that $-1$ is a quadratic residue $\pmod{p}$ and thus, there always exists a root $r$ of $f(x) \pmod{p}$. Let $v_p(a_n(a_n+1))=k$. Next since $f'(r) = 2r \not \equiv 0 \pmod{p}$, by Hensel's Lemma it follows that there exists a unique root $r^* \pmod{p^k}$ of $f(x) \pmod{p^k}$. Now, by the Chinese Remainder Theorem, we are guaranteed that there exists some positive integer $b \pmod{a_n(a_n+1)}$ such that $b_n^2 +1$ is divisible by $a_n(a_n+1)$. In order to satisfy the strictly increasing condition of $b_n$ simply add multiples of $a_n(a_n+1)$ to such $b$ as required, to obtain a pair of sequences which satisfy the given conditions.

We will rephrase the problem as the following. Problem. Prove that for every positive integer $M$, there exists some positive integer $a>M$ such that there is a positive integer $b$ with $a(a+1)\mid b^2+1$. Firstly, we will characterize all types of numbers that can divide $b^2+1$. I claim that for positive integers $n$, there exists some $b$ such that $n\mid b^2+1$ if and only if $\nu_2(n)\le 1$, and $n$ does not have any $3$ mod $4$ prime factors. Clearly this is necessary (mod $4$ and Fermat's Christmas Theorem), and note that CRT allows us to only prove this for prime powers. We can prove it for $2$ easily, and for $p^k$ where $p\equiv 1\pmod 4$, we can use Hensel's lemma. Consider the solutions to the Pell equation $x^2-5y^2=5$. We know that there are infinitely many of these (this is more obvious if we do $x\rightarrow 5x'$). Note that $x^2+1=5(y^2+1)+1$, so if we let $a=5(y^2+1)$, we get that $a(a+1)$ has only $1$ mod $4$ prime factors, with the exception of at most one $2$ (since they are consecutive, only one can be even, and then it must be $2$ mod $4$), so we win. $\blacksquare$