TAOCP 4.3.2 Exercise 11
Let u \equiv u_j \pmod{m_j}, \qquad 0\le u_j<m_j \qquad (1\le j\le r), where the moduli $m_j$ are odd and $u$ is known to be even.
Section 4.3.2: Modular Arithmetic
Exercise 11. [M23] Assume that all the $m_j$ are odd, and that $u = (u_1, \ldots, u_r)$ is known to be even, where $0 \le u < m$. Find a reasonably fast method to compute $u/2$ using modular arithmetic.
Verified: yes
Solve time: 3m
Solution
Let
$$ u \equiv u_j \pmod{m_j}, \qquad 0\le u_j<m_j \qquad (1\le j\le r), $$
where the moduli $m_j$ are odd and $u$ is known to be even.
We seek the residue representation of
$$ v=\frac u2. $$
For each modulus $m_j$ we must determine
$$ v_j \equiv v \pmod{m_j}. $$
Since $u=2v$,
$$ 2v_j \equiv u_j \pmod{m_j}. \tag{1} $$
Because $m_j$ is odd, $\gcd(2,m_j)=1$; therefore $2$ has a multiplicative inverse modulo $m_j$, and (1) has a unique solution modulo $m_j$.
A division by $2$ can be performed without explicitly computing the inverse. If $u_j$ is even, then
$$ v_j=\frac{u_j}{2} $$
satisfies (1), since
$$ 2v_j=u_j. $$
If $u_j$ is odd, then
$$ u_j+m_j $$
is even because $m_j$ is odd. Hence
$$ v_j=\frac{u_j+m_j}{2} $$
satisfies
$$ 2v_j=u_j+m_j\equiv u_j \pmod{m_j}. $$
Thus
$$ v_j= \begin{cases} u_j/2, & u_j \text{ even},\[4pt] (u_j+m_j)/2, & u_j \text{ odd}. \end{cases} \tag{2} $$
Equivalently,
$$ v_j=\frac{u_j+m_j[u_j\ \text{odd}]}{2}. \tag{3} $$
For every $j$,
$$ 0\le v_j<m_j, $$
since $0\le u_j<m_j$ and
$$ 0\le \frac{u_j+m_j}{2}<m_j. $$
Therefore the residues $(v_1,\ldots,v_r)$ are in standard form.
To prove that these residues represent $u/2$, let $v$ be the integer determined by Theorem C from the residues (2). Then for every $j$,
$$ 2v \equiv 2v_j \equiv u_j \equiv u \pmod{m_j}. $$
Hence
$$ 2v \equiv u \pmod m, $$
where $m=m_1m_2\cdots m_r$, by Theorem C.
Since $u$ is even, $2v-u$ is even. Because $m$ is odd, $\gcd(2,m)=1$; therefore
$$ m \mid (2v-u) \quad\Longrightarrow\quad m \mid \left(v-\frac u2\right). $$
Both $v$ and $u/2$ lie in the interval $0\le x<m$, so Theorem C implies
$$ v=\frac u2. $$
Hence a fast modular-arithmetic division by $2$ is obtained by replacing each residue $u_j$ independently according to (2):
$$ \boxed{\displaystyle \left(\frac u2\right)_j = \frac{u_j+m_j[u_j\ \text{odd}]}{2} \qquad (1\le j\le r). } $$
This completes the proof.
∎