TAOCP 4.3.2 Exercise 5
Let M=m_1m_2\cdots m_r, where the $m_j$ are odd positive integers $<100$ and are pairwise relatively prime.
Section 4.3.2: Modular Arithmetic
Exercise 5. ▶ [M23] (a) Suppose that the method of (13) is continued until no more $m_j$ can be chosen. Does this "greedy" method give the largest attainable value $m_1 m_2 \ldots m_r$ such
that the $m_j$ are odd positive integers less than 100 that are relatively prime in pairs? (b) What is the largest possible $m_1 m_2 \ldots m_r$ when each residue $u_j$ must fit in eight bits of memory?
Verified: yes
Solve time: 3m03s
Let
$$ M=m_1m_2\cdots m_r, $$
where the $m_j$ are odd positive integers $<100$ and are pairwise relatively prime.
The condition of pairwise relative primality implies that each odd prime $p<100$ can divide at most one of the $m_j$.
Therefore the contribution of each prime can be considered independently.
(a) Does the greedy method maximize $M$?
The method of (13) chooses successively the largest odd integer $<100$ that is relatively prime to all previously chosen choices. It begins
$$ 99=3^2\cdot11,\qquad 97,\qquad 95=5\cdot19,\qquad 91=7\cdot13,\qquad 89,\qquad 83,\ldots $$
To maximize $M$, observe that every odd prime $p<100$ should be used exactly once. If a prime is omitted, multiplying one of the moduli by $p$ would increase the product while preserving pairwise relative primality.
Hence the problem is to partition the odd primes $<100$ into factors $<100$ so that the resulting product is as large as possible.
For a prime $p$, let $e_p$ be the largest exponent such that
$$ p^{e_p}<100. $$
Then the greatest possible contribution of $p$ is $p^{e_p}$, since all powers of $p$ must occur in a single modulus and no modulus may reach $100$.
The admissible maximal powers are
$$ 3^4=81,\qquad 5^2=25,\qquad 7^2=49, $$
and for every odd prime $p\ge 11$,
$$ p^2>99, $$
so only the first power may be used.
Therefore the largest attainable product is
$$ M_{\max} = 81\cdot25\cdot49 \prod_{11\le p<100} p. $$
The greedy construction does not produce this value, because it chooses
$$ 99=3^2\cdot11 $$
instead of $81=3^4$, and
$$ 95=5\cdot19 $$
instead of $25=5^2$, etc.
Indeed,
$$ 81\cdot25\cdot49 = 99225, $$
while the corresponding contribution from the greedy choices is
$$ 99\cdot95\cdot91 = 856,635. $$
Comparing prime exponents,
$$ 99\cdot95\cdot91 = 3^2\cdot5\cdot7\cdot11\cdot13\cdot19, $$
whereas
$$ 81\cdot25\cdot49 = 3^4\cdot5^2\cdot7^2. $$
After cancelling the common primes $11,13,19$,
$$ \frac{81\cdot25\cdot49} {99\cdot95\cdot91/(11\cdot13\cdot19)} = \frac{3^4\cdot5^2\cdot7^2} {3^2\cdot5\cdot7} = 3^2\cdot5\cdot7 = 315>1. $$
Hence replacing the greedy choices by $81,25,49$ yields a larger product.
Therefore the greedy method does not give the largest attainable value of $M$.
(b) Largest possible product when each residue $u_j$ must fit in eight bits
In the mixed-radix representation of Theorem C, each residue satisfies
$$ 0\le u_j<m_j. $$
If each $u_j$ must fit in eight bits, then
$$ u_j\le 255. $$
Since every modulus under consideration satisfies
$$ m_j<100<256, $$
every possible residue already fits into eight bits.
Thus the eight-bit restriction imposes no additional constraint. The problem is exactly the same as in part (a).
Consequently the largest possible product is
$$ \boxed{ M_{\max} = 81\cdot25\cdot49 \prod_{11\le p<100} p }. $$
Using the odd primes
$$ 11,13,17,19,23,29,31,37,41,43,47, 53,59,61,67,71,73,79,83,89,97, $$
this may be written as
$$ \boxed{ M_{\max} = 81\cdot25\cdot49\cdot 11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot41\cdot43\cdot47 \cdot53\cdot59\cdot61\cdot67\cdot71\cdot73\cdot79\cdot83\cdot89\cdot97 }. $$
Therefore:
$$ \boxed{\text{(a) No.}} $$
$$ \boxed{\text{(b) The maximum product is } 81\cdot25\cdot49\prod_{11\le p<100}p.} $$