# Modified Euclidean Algorithm

**Number Theory**Level 5

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.

**Your answer seems reasonable.**Find out if you're right!

**That seems reasonable.**Find out if you're right!

Already have an account? Log in here.