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.


Problem Loading...

Note Loading...

Set Loading...