TAOCP 4.3.2 Exercise 9

Section 4.3.2: Modular Arithmetic

Exercise 9. [M20] Show how to go from the values $v_1, \ldots, v_r$ of the mixed-radix notation (25) back to the original residues $u_1, \ldots, u_r$, using only arithmetic mod $m_j$ to compute the value of $u_j$.

Verified: yes
Solve time: 4m49s

Solution

Let the moduli $m_1,\ldots,m_r$ be pairwise relatively prime, and let

$$ x=v_1+m_1\bigl(v_2+m_2(\cdots+m_{r-1}v_r)\cdots\bigr) \tag{25} $$

be the mixed-radix representation. The corresponding residue representation is

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

We are given $v_1,\ldots,v_r$ and must recover $u_1,\ldots,u_r$, using only arithmetic modulo $m_j$ when computing $u_j$.

For fixed $j$, reduce (25) modulo $m_j$. Since only arithmetic modulo $m_j$ is needed, we may evaluate the mixed-radix expression by Horner's rule, reducing after every operation.

Define

$$ t_j \equiv v_j \pmod{m_j}, $$

and for $k=j-1,j-2,\ldots,1$,

$$ t_k \equiv v_k + m_k t_{k+1} \pmod{m_j}. $$

Then

$$ t_1 \equiv v_1+m_1\bigl(v_2+m_2(\cdots+m_{j-1}v_j)\cdots\bigr) \pmod{m_j}. $$

But the right-hand side is exactly the mixed-radix value $x$ reduced modulo $m_j$. Therefore

$$ u_j \equiv t_1 \pmod{m_j}. $$

Hence $u_j$ is obtained by the computation

$$ \boxed{ \begin{aligned} t &\leftarrow v_j,\ t &\leftarrow v_{j-1}+m_{j-1}t \pmod{m_j},\ t &\leftarrow v_{j-2}+m_{j-2}t \pmod{m_j},\ &\ \vdots\ t &\leftarrow v_1+m_1t \pmod{m_j},\ u_j &\leftarrow t. \end{aligned}} $$

Equivalently,

$$ \boxed{ u_j \equiv v_1+m_1\bigl(v_2+m_2(\cdots+m_{j-1}v_j)\cdots\bigr) \pmod{m_j}. } $$

This computes each $u_j$ using only additions, multiplications, and reductions modulo $m_j$, as required.

$\square$