Find all solution to $a^{2}\equiv -1 \pmod b$ and $b^{2}\equiv -1\pmod a$ (self-answer) There was a question here just a moment ago but was deleted by the author. It is to find all solution to $a^{2}\equiv -1 \pmod b$ and $b^{2}\equiv -1 \pmod a$ with $a,b>1$. But I already typed up the solution, and don't want it to go to waste. So I'm posting this with answer.
However, feel free to add your own solution too!
 A: EDIT: reorganize:
Consider a solution $a,b$. (edit:now we no longer assume that $a<b$)
We have $b|(a^{2}+1)$ so let $c=\frac{a^{2}+1}{b}$. Now $(a^{2}+1)^{2}\equiv 1(\mod a)$. Hence $b^{2}c^{2}\equiv 1(\mod a)$. But $b^{2}\equiv -1(\mod a)$ hence $c^{2}\equiv -1(\mod a)$. Easily see that $a^{2}\equiv -1(\mod c)$. Thus $c,a$ is also a solution to the problem. Note that if $b<a$ then $c>a$ and vice versa.
Use infinite descend we eventually end up having a solution where $c=1$. That is $b=a^{2}+1$. Hence $a^{4}+2a^{2}+1\equiv -1(\mod a)$ which force $1\equiv -1(\mod a)$ so $a=2$ and $b=5$. Note that no matter what $a,b$ we start with at the beginning, we always end up with this value $2,5$.
EDIT: Here is a more rigorous way of doing it:
We define an unique sequence $a_{i}$ where $a_{1}=2,a_{2}=5$ and $a_{n+1}=\frac{a_{n}^{2}+1}{a_{n-1}}$ for $n\geq 2$. From this definition it is immediately obvious that if $a_{n-1}<a_{n}$ then $a_{n}<a_{n+1}$ and so by induction this sequence is strictly increasing.
We have for any $n$ if $a_{n-1},a_{n}$ is a solution, $a_{n},a_{n+1}$ is a solution (remember, if $a,b$ is a solution then $\frac{a^{2}+1}{b},a$ is also a solution; and here we apply $a=a_{n},b=a_{n-1}$). Now we do in fact have $a_{1},a_{2}$ being a solution. Hence by induction, any $a_{i},a_{i+1}$ is a solution.
Assuming that there is a solution not in the form $a_{i},a_{i+1}$. If $a=b$ then immediately we have $0\equiv -1(\mod a)$ forcing $a=b=1$ which not allowed. So there must exist a solution $1<a<b$ not in the sequence with minimum $a+b$. Let $c=\frac{a^{2}+1}{b}$. Then apply the argument above, $c,a$ is a solution with $c<a<b$ so $c+a<a+b$. Hence $c,a$ is in the sequence (due to the minimum assumption) so we have either $c=a_{i-1},a=a_{i}$ or $c=a_{i},a=a_{i-1}$. But $c<a$ so the 2nd possibility is impossible because the sequence is strictly increasing. Hence the 1st possibility must happened. Hence $b=\frac{a^{2}+1}{c}=\frac{a_{i}^{2}+1}{a_{i-1}}=a_{i+1}$ which means $a,b$ is in fact $a_{i},a_{i+1}$ contradicting the assumption that this is not.
Hence all solutions are of the form $a_{i},a_{i+1}$.
Now prove, once again by infinite descend, that $a,b$ are consecutive odd index Fibonacci number then $b^{2}-b(b-a)-a^{2}=1$ (hint: show that $a^{2}-a(b-2a)-(b-2a)^{2}=b^{2}-b(b-a)-a^{2}$ and do infinite descend by replacing $a,b$ with $3a-b,a$.). Using that, we showed that all consecutive odd index Fibonacci number satisfied $b^{2}-b(b-a)-a^{2}=1$. But expand that one out give us $-b^{2}+3ab-a^{2}=1$ which means $b^{2}\equiv -1(\mod a)$ and $a^{2}\equiv -1(\mod b)$. That is consecutive odd index Fibonacci number are always solution.
Let $b_{n}$ be the $(2n+1)$-th Fibonacci number. Then $b_{1}=2=a_{1},b_{2}=5=a_{2}$, and $b_{i}<b_{i+1}$ are always solution.
Now we use induction again. If $b_{n}=a_{n}$ for some $i$, then since $b_{n},b_{n+1}$ is a solution, and all solution is of the form $a_{i},a_{i+1}$ we must have either $b_{n+1}=a_{n-1}$ or $b_{n+1}=a_{n+1}$. But $a_{n-1}<a_{n}=b_{n}<b_{n+1}$ hence the first possibility is not possible. Thus $b_{n+1}=a_{n+1}$. We already checked the base case. Hence by induction $b_{n}=a_{n}$ for all $n$.
Thus all solutions are consecutive odd index Fibonacci number.
