Find the number of coprime pairs $(a,b)$ of positive integers subject to $0< a<b<10^{100},$ such that

$a|(b^2-11) , b|(a^2-11).$

The answer is 582.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

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.