TAOCP 4.3.2 Exercise 4

Exercise 4. [29] Continue the process shown in (13); what would $m_5, m_6, m_9, \ldots$ be?

Verified: yes
Solve time: 4m40s

Equation (13) is obtained by choosing successively the largest odd integer below the preceding modulus that is relatively prime to every modulus already chosen.

The first four terms are

$$ m_1=99,\qquad m_2=97,\qquad m_3=95,\qquad m_4=91. $$

We continue the process.

Since

$$ 99=3^2\cdot11,\qquad 95=5\cdot19,\qquad 91=7\cdot13, $$

every later modulus must avoid the prime factors

$$ 3,5,7,11,13,19, $$

and also any new prime factors introduced later.

For $m_5$, examine odd numbers below $91$:

$$ 89 $$

is relatively prime to $99,97,95,91$. Hence

$$ m_5=89. $$

For $m_6$, examine odd numbers below $89$:

$$ 87=3\cdot29,\qquad 85=5\cdot17, $$

so both are excluded. Next,

$$ 83 $$

is relatively prime to all previous moduli. Therefore

$$ m_6=83. $$

For $m_7$, examine odd numbers below $83$:

$$ 81=3^4 $$

shares a factor with $99$, hence is excluded. The next candidate is $79$, which is relatively prime to all previous moduli. Thus

$$ m_7=79. $$

For $m_8$, examine odd numbers below $79$:

$$ 77=7\cdot11,\qquad 75=3\cdot5, $$

so both are excluded. The next candidate,

$$ 73, $$

is relatively prime to all earlier moduli. Hence

$$ m_8=73. $$

For $m_9$, examine odd numbers below $73$:

$$ 71 $$

is relatively prime to every previous modulus, so

$$ m_9=71. $$

Therefore

$$ \boxed{m_5=89,\qquad m_6=83,\qquad m_9=71.} $$

The continued sequence begins

$$ 99,\ 97,\ 95,\ 91,\ 89,\ 83,\ 79,\ 73,\ 71,\ldots $$

which is obtained by repeatedly taking the largest admissible odd integer relatively prime to all previously chosen moduli.