TAOCP 4.3.2: Modular Arithmetic
Section 4.3.2 exercises: 14/14 solved.
Section 4.3.2. Modular Arithmetic
Exercises from TAOCP Volume 2 Section 4.3.2: 14/14 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [39] | project | verified | 4m13s |
| 2 | ▶ [M20] | math-medium | verified | 3m43s |
| 3 | ▶ [M26] | math-hard | verified | 9m |
| 4 | [29] | hard | verified | 4m40s |
| 5 | ▶ [M23] | math-medium | verified | 3m03s |
| 6 | [M22] | math-medium | solved | 7m12s |
| 7 | ▶ [M31] | math-hard | verified | 2m32s |
| 8 | [M31] | math-hard | verified | 1m29s |
| 9 | [M20] | math-medium | verified | 4m49s |
| 10 | [M25] | math-medium | verified | 2m14s |
| 11 | [M23] | math-medium | verified | 3m |
| 12 | [M10] | math-simple | verified | 1m50s |
| 14 | ▶ [M50] | math-research | verified | 1m59s |
| 33 | ▶ [M25] | math-medium | verified | 5m15s |
TAOCP 4.3.2 Exercise 1
Find all integers $u$ such that u \bmod 7 = 1,\qquad u \bmod 11 = 0,\qquad u \bmod 13 = 5,
TAOCP 4.3.2 Exercise 2
No.
TAOCP 4.3.2 Exercise 3
Let m=\operatorname{lcm}(m_1,m_2,\ldots,m_r).
TAOCP 4.3.2 Exercise 4
Equation (13) is obtained by choosing successively the largest odd integer below the preceding modulus that is relatively prime to every modulus already chosen.
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.
TAOCP 4.3.2 Exercise 6
We claim that 2^e \equiv 2^f \pmod{2^g - 1} \quad \Longleftrightarrow \quad e \equiv f \pmod{g}.
TAOCP 4.3.2 Exercise 7
Let M_i=m_1m_2\cdots m_i , and recall that in Knuth's derivation of (24) the constants $c_{ij}$ ($i<j$) satisfy
TAOCP 4.3.2 Exercise 8
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).
TAOCP 4.3.2 Exercise 9
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.
TAOCP 4.3.2 Exercise 10
Suppose an integer $u$ satisfies $-m/2 < u < m/2$, where $m = m_1 m_2 \cdots m_r$, and consider a modular representation of $u$ using symmetric residues $u_1, \ldots, u_r$ such that $-m_j/2 < u_j < m_...
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.
TAOCP 4.3.2 Exercise 12
Suppose $0 \le u, v < m$, and let $w = u + v$ computed in a modular representation with moduli $m_1, \ldots, m_r$.
TAOCP 4.3.2 Exercise 14
We are asked to compute the representation of $w = (uv) \bmod (2^q - 1)$ for $q$-bit integers $u$ and $v$ that are expressed in a nonuniform radix representation $u = \sum_{k=0}^{n-1} u_k 2^{\lfloor k...