11 Is Not A Typo

This problem is an example of the Vieta Root Jumping technique. One may want to look at simpler Vieta Root Jumping problems first before jumping (pun intended) into this one.

First, note that for coprime pairs $a,b$ the conditions $a|(b^2-11),$ and $b|(a^2-11)$ are equivalent to a single condition: $ab|(a^2+b^2-11).$

Suppose $\frac{a^2+b^2-11}{ab}=n.$ This can be rewritten as $b^2-nab+(a^2-11)=0$ So $b$ is one of the roots of the quadratic equation $x^2-(na)x+(a^2-11)=0.$ The other root, which is also integer, can be written as $c=na-b$ or $\frac{a^2-11}{b}$ .

If $a^2-11>0,$ then $a^2-11,a^2<ab,$ so $0<c<a$ . Also, $gcd(c,a)=gcd(na-b,a)=gcd(a,b)=1.$ Therefore, the pair $(c,a)$ also satisfies the same conditions as $(a,b),$ for the same $n.$

We apply the above argument repeatedly to any solution $(a,b)$ until we get a pair $(a_0,b_0)$ such that $a_0^2-11<0$ . Note that we can recover the original solution by "jumping back": in the argument above $(a,b)=(a,na-c).$

If $a_0^2-11<0,$ we get, since $a_0>0,$ three possibilities: $a_0=1,2,3$ .

Case 1. $a_0=3.$ Then $b_0^2-3nb_0-2=0,$ so $b_0(b_0-3n)=2.$ This implies $b_0\leq 2,$ which contradicts $a_0<b_0.$ So this case is impossible.

Case 2. $a_0=2.$ Then, similar to the above, we get $b_0(b_0-2n)=7.$ Since $b_0 > a_0,$ this implies that $b_0=7.$ So $n=3.$ By jumping back this pair $(a_0,b_0)$ leads to solutions $(u_i,u_{i+1}),$ where the sequence $\{u_i\}$ is given by condition $u_0=2,u_1=7; u_{i+1}=3u_n-u_{n-1}:$ $2,7,19,50,131,343,...$

Case 3. $a_0=1.$ Then we get $b_0(b_0-n)=10.$ This has three solutions: $b_2,n=-3,$ $b_0=5,n=3,$ and $b=10,n=9$ . Note that the first pair, $(a_0,b_0)=(1,2),$ cannot be jumped into, because $b^2-11$ is already negative, so the process would have stopped one step earlier. The other two pairs do lead to infinite series of solutions. The pair $(1,5)$ gives a sequence $(v_i,v_{i+1}),$ where $v_0=1,v_1=5;v_{i+1}=3v_i-v_{i-1}.$ The pair $(1,10)$ gives a sequence $(w_i,w_{i+1}),$ where $w_0=1,w_1=10;w_{i+1}=9w_i-w_{i-1}.$

In order to count the number of solutions with $b<10^{100}$ we need to find out how fast these sequences grow. Note that they are similar to the Fibonacci sequences, and grow exponentially. The general theory of linear recursive sequences allows us to find the formulas for them.

Lemma. Suppose $s=\frac{3+\sqrt{5}}{2}$ and $t=\frac{9+\sqrt{77}}{2}.$ Then for all $i$ we have $u_i=\frac{\sqrt{5}+4}{\sqrt{5}}s^i+\frac{\sqrt{5}-4}{\sqrt{5}}s^{-i},$

$v_i=\frac{\sqrt{5}+7}{2\sqrt{5}}s^i+\frac{\sqrt{5}-7}{2\sqrt{5}}s^{-i},$

$w_i=\frac{\sqrt{7}+\sqrt{11}}{2\sqrt{7}}t^i+\frac{\sqrt{7}-\sqrt{11}}{2\sqrt{11}}t^{-i}.$

Proof. Note that $s$ and $s^{-1}$ are the two roots of the equation $x^2=3x-1,$ while $t$ and $t^{-1}$ are the two roots of $x^2=9x-1.$ The general theory implies that $u_i=\alpha s^i + \beta s^{-i}$ for some $\alpha$ and $\beta$ . Using $i=0$ and $i=1,$ we get $\alpha=\frac{\sqrt{5}+4}{\sqrt{5}}$ and $\beta=\frac{\sqrt{5}-4}{\sqrt{5}}$ . The resulting formula is easy to prove by induction. The other two formulas are obtained in the same way.

Now note that $s^{-1}$ and $t^{-1}$ are less than $1,$ so their powers decay exponentially. So for large $i$ $u_i$ is approximately equal to $\frac{\sqrt{5}+4}{\sqrt{5}}s^i.$ So using logarithms, one can easily check that the largest $u_i<10^{100}$ is $u_{238}.$ Likewise, the largest $v_i<10^{100}$ is $v_{238},$ and the largest $w_i<10^{100}$ is $w_{105}.$

So, we have a pair $(1,2),$ $238$ pairs of type $u,$ $239$ pairs of type $v,$ and $105$ pairs of type $w.$ This gives $1+238+238+105=582$ pairs.

I write a python program to solve it (execute time: 0.4s)

import math
from fractions import gcd

test = 1
max_num = 10 ** 100

lstb = [1, 2, 5, 10, 7]

a = 2
b = 0
while a < max_num:
    newa = a + 1
    isSet = False
    for tmp in lstb:            
        if tmp <= a:
            continue
        if not isSet:
            newa = tmp
            isSet = True
        if tmp < newa:
            newa = tmp
    a = newa

    a2 = a ** 2

    foundB = False


    for x in lstb :
        if (a2 - 11) % x == 0:
            candidate = (a2 - 11) // x

            b2 = candidate ** 2
            if (b2 - 11) % a == 0:                  
                print(a, candidate)
                lstb.append(candidate)
                b = candidate
                foundB = True
                break

print(len(lstb) - 1)

count = 0
for tmp in lstb:
    if tmp > 1 and tmp < max_num:
        count += 1

print(count)