TAOCP 4.3.2 Exercise 12

Section 4.3.2: Modular Arithmetic

Exercise 12. [M10] Prove that, if $0 \le u, v < m$, the modular addition of $u$ and $v$ causes overflow (lies outside the range allowed by the modular representation) if and only if the sum is less than $u$. (Thus the overflow detection problem is equivalent to the comparison problem.)

Verified: yes
Solve time: 1m50s

Suppose $0 \le u, v < m$, and let $w = u + v$ computed in a modular representation with moduli $m_1, \ldots, m_r$. Overflow occurs when $w$ lies outside the range $0 \le w < m$ allowed by the representation. If no overflow occurs, then $w \ge u$ because $v \ge 0$. Conversely, if overflow occurs, the computed sum $w$ wraps around modulo $m$, giving $w \equiv u + v \pmod{m}$ with $0 \le w < m$, but since $u + v \ge m$, we have $w = u + v - m < u$. Therefore overflow occurs if and only if the sum $w$ is less than $u$. This shows that detecting overflow is equivalent to comparing $w$ with $u$.

This completes the proof.

∎