How Many Good Pairs?

Claim: $(m, n)$ is a good pair if and only if so is $\left( \dfrac{m^2+1}{n}, m \right).$

Proof: Let $x = \dfrac{m^2+1}{n}.$ We trivially have $x \mid m^2+1.$ Note that $\gcd (x, m) = \gcd (n, m)= 1,$ and $xn \equiv 1 \pmod{m},$ so $x^2 + 1 \equiv \left( \dfrac{1}{n} \right) ^2 + 1\equiv \dfrac{n^2+1}{n} \equiv 0 \pmod{m},$ so $m$ divides $x^2+1.$ Hence $\left( \dfrac{m^2+1}{n}, m \right)$ is good. Conversely, if $\left( \dfrac{m^2+1}{n}, m \right)$ is good, so must be $\left( \dfrac{m^2+1}{(m^2+1)/n}, m \right) = (n, m).$ The claim is proved. $\blacksquare$

By the claim, given any good pair $(m, n),$ we can successively apply the operation $(m, n) \rightarrow \left( m, \dfrac{m^2+1}{n} \right)$ and eventually arrive at a good pair of the form $(1, \alpha)$ for some $\alpha \in \mathbb{N}.$ Since $\alpha$ divides $1^2+1= 2,$ $\alpha$ is either $1$ or $2.$ We shall now reconstruct our solutions from this.

• If $\alpha = 1,$ applying the operation backwards gives the following good pairs. $(1, 1) \rightarrow (2, 1) \rightarrow (5, 2) \rightarrow \cdots$
• We get the same solutions except $(1, 1)$ when $\alpha = 2.$

Let $F_k$ denote the $k^{\text{th}}$ Fibonacci number. We claim that all good pairs are of the form $(F_{2k-1}, F_{2k+1}).$ The proof is by induction. The base case $k=1$ holds true, since $(F_{2 \cdot 1 - 1}, F_{2 \cdot 1 + 1}) = (1, 2)$ is indeed a good pair. For the inductive step, assume it is true for some $k \in \mathbb{N_{\geq 1}}.$ By our reverse operation, the next solution is given by $\left( \dfrac{F_{2k-1}^2 + 1}{F_{2k+1}}, F_{2k+1} \right) = (F_{2k+1}, F_{2k+3}),$ where we have used the well known identity $F_{n-1} F_{n+1} - F_n^2= (-1)^n \quad \ \forall n \in \mathbb{N}.$ Hence, all admissible integers are the Fibonacci numbers with an odd index. All such integers less than $100$ are $1, 2, 5, 13, 34, 89,$ and their sum is $\boxed{144}.$