Given a positive integer $n$, find the number of pairs $(a,b)$ where $a,b\in\mathbb N$ such that $(a^2-1)$ is divisible by $b$ and $(b^2-1)$ is divisible by $a$, and where $1 \le a < b \le n$.
Please help me how to solve this problem in constant time complexity. Thank you.
Clearly $(1,b)$ works always, so we concentrate on the other solutions.
Suppose we have $a$ and $b$ such that $a|(b+1)(b-1)$ and $b|(a+1)(a-1$).
Lemma $1$: Since $(a+1,a-1)=2$ or $1$ we have $a|2(b+1)$ or $a|2(b-1)$.
Lemma $2$: If $a$ is odd then $a|(b+1)$ or $a|(b-1)$. In particular $a\leq b+1$
Clearly $a$ and $b$ can't both be even.
If $a$ and $b$ are both odd by the lemma we have $a\leq b+1$ and $b\leq a+1$, so the only options are $(n,n+1)$ and $n,n$, of course only $(n,n)$ can have both odd. And clearly $(n,n)$ only works if $n=1$.
We now assume $a$ is odd and $b$ is even.
Case $1: a|(b-1)$, if $a\neq b-1$ then $a\leq (b-1)/3$ (because $(b-1)$ is odd). Notice that we must have $b|2(a+1)$ or $b|2(ba-1)$ which implies $2a+2\geq b$.
We have $a\leq(b-1)/3\implies 3a+1\leq b$ and $2a+2\geq b$, which would imply $a=1$. So the only possible solution is $a=b-1$, or $(a,a+1)$ which clearly always works.
Case $2$: $a|b+1$, if $a\neq b+1$ then $a\leq(b+1)/3$ (because $b+1$ is odd). Notice we have $b|2(a+1)$ or $b|2(a-1)$ which implies $2a+1\geq b$.
We have $a\leq(b+1)/3\implies 3a-1\leq b$ and $2a+2\geq b$, which would imply $a=1,2$ or $3$. When $a=2$ clearly $b$ must divide $2^2-1=3$, and $(2,3)$ works. When $a=3$ clearly $b$ must be $1,2,4$ or $8$. We notice $(3,8)$ works. So the only other option is $a=b+1$.
So the only solutions are: $(1,b),(a,1),(a,a+1),(b+1,b),(3,8)$