# Modified Euclidean Algorithm

The following procedure is a modified Euclidean algorithm. For a pair $(n,m)$ of positive integers with $n we construct a sequence of pairs of positive integers $(n_0,m_0), \ (n_1,m_1),\ ...$ such that $(n_0,m_0)=(n,m)$ and for all $i\geq 0$ $m_{i+1}=n_i;\ n_{i+1}=\min (r_i,n_i-r_i),$ where $r_i$ is the remainder of $m_i$ divided by $n_i$. We repeat this procedure until we get a pair $(n_k,m_k)$ with $n_k \mid m_k$, so that $r_k=0$ and the algorithm terminates.

Find the number of pairs $(101,m)$ with $101 for which this algorithm terminates in no more than $4$ steps with $n_k=1$ (that is, $n_k=1$ for $k\leq 4$).

Details and assumptions

Example: If $(n,m)=(101,215)$, then $(n_0,m_0)=(101,215),$ $(n_1,m_1) =(13,101),$ $(n_2,m_2)=(3,13),$ $(n_3,m_3) = (1,3)$, so for the pair $(101,225)$ the algorithm terminates with $n_k=1$ in $3$ steps.

×