TAOCP 4.3.2 Exercise 8

Exercise 8. [M31] Prove that the number $u$ defined by (24) and (25) satisfies (26).

Verified: yes
Solve time: 1m29s

Setup

Let $(u_1,\ldots,u_r)$ be a modular representation with pairwise relatively prime moduli $m_1,\ldots,m_r$, and let $u$ be reconstructed by the procedure defined in equations (24) and (25).

Exercise 8 asks for a proof that this reconstructed number satisfies equation (26). In other words, one must show that the value of $u$ obtained from (24) and (25) has the prescribed residues modulo each modulus $m_j$.

The reconstruction formulas are the mixed-radix conversion formulas. Equation (24) defines the digits $v_1,\ldots,v_r$ recursively, and equation (25) defines

$$ u=v_1+m_1v_2+m_1m_2v_3+\cdots+m_1m_2\cdots m_{r-1}v_r. $$

Equation (26) asserts that

$$ u\equiv u_j \pmod{m_j}, \qquad 1\le j\le r. $$

This is what must be proved.

Solution

Define

$$ U_k=v_1+m_1v_2+\cdots+m_1m_2\cdots m_{k-1}v_k, \qquad 1\le k\le r. $$

Thus $U_r=u$ by (25).

The recursive definition (24) determines $v_k$ by

$$ v_k\equiv \bigl(u_k-U_{k-1}\bigr) c_{1k}c_{2k}\cdots c_{k-1,k} \pmod{m_k}, $$

where each constant $c_{ik}$ is the inverse of $m_i$ modulo $m_k$:

$$ m_i c_{ik}\equiv1\pmod{m_k}. $$

Multiplying the congruence for $v_k$ by $m_1m_2\cdots m_{k-1}$ gives

$$ m_1m_2\cdots m_{k-1}v_k \equiv u_k-U_{k-1} \pmod{m_k}, $$

because

$$ (m_1c_{1k})(m_2c_{2k})\cdots(m_{k-1}c_{k-1,k}) \equiv1 \pmod{m_k}. $$

Hence

$$ U_k = U_{k-1}+m_1m_2\cdots m_{k-1}v_k \equiv u_k \pmod{m_k}. $$

Therefore

$$ U_k\equiv u_k\pmod{m_k}. \tag{1} $$

The same construction preserves all previously established congruences. For $j<k$, the difference

$$ U_k-U_{k-1} = m_1m_2\cdots m_{k-1}v_k $$

contains the factor $m_j$; therefore

$$ U_k\equiv U_{k-1}\pmod{m_j}. $$

Applying this repeatedly yields

$$ U_k\equiv U_j\pmod{m_j}. $$

Combining this with (1) for index $j$ gives

$$ U_k\equiv u_j\pmod{m_j}, \qquad j\le k. \tag{2} $$

Take $k=r$. Since $U_r=u$, equation (2) becomes

$$ u\equiv u_j\pmod{m_j}, \qquad 1\le j\le r. $$

This is precisely equation (26).

Thus the number $u$ defined by (24) and (25) satisfies all of the required congruences.

This completes the proof.

∎

Verification

For each stage $k$:

$$ U_k=U_{k-1}+m_1m_2\cdots m_{k-1}v_k. $$

The choice of $v_k$ in (24) ensures

$$ m_1m_2\cdots m_{k-1}v_k \equiv u_k-U_{k-1} \pmod{m_k}, $$

hence

$$ U_k\equiv u_k\pmod{m_k}. $$

For every $j<k$,

$$ m_j\mid m_1m_2\cdots m_{k-1}, $$

$$ U_k\equiv U_{k-1}\pmod{m_j}. $$

Consequently all congruences already established remain valid. After the final stage,

$$ u=U_r $$

satisfies

$$ u\equiv u_j\pmod{m_j} \qquad(1\le j\le r), $$

which is exactly (26).

Notes

The proof shows more than the statement of the exercise. After the $k$th mixed-radix digit has been determined, the partial value $U_k$ already satisfies

$$ U_k\equiv u_j\pmod{m_j}, \qquad 1\le j\le k. $$

Thus the conversion algorithm successively incorporates one additional modulus while preserving all congruences obtained earlier.