# Modified Euclidean Algorithm

The following procedure is a modified Euclidean algorithm. For a pair $$(n,m)$$ of positive integers with $$n<m$$ 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<m<1000$$ 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.

×