TAOCP 4.6.1: Division of Polynomials
Section 4.6.1 exercises: 26/26 solved.
Section 4.6.1. Division of Polynomials
Exercises from TAOCP Volume 2 Section 4.6.1: 26/26 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [10] | simple | verified | 5m45s |
| 2 | [15] | simple | solved | 9m29s |
| 3 | ▶ [M25] | math-medium | solved | 16m29s |
| 4 | [M30] | math-hard | verified | 2m51s |
| 5 | [M22] | math-medium | verified | 4m23s |
| 6 | [M29] | math-hard | solved | 10m41s |
| 7 | [M10] | math-simple | verified | 1m54s |
| 8 | ▶ [M22] | math-medium | solved | 1m28s |
| 9 | [M25] | math-medium | verified | 6m26s |
| 10 | [M28] | math-hard | verified | 1m47s |
| 11 | [M22] | math-medium | verified | 4m17s |
| 12 | ▶ [M24] | math-medium | verified | 5m08s |
| 13 | [M22] | math-medium | solved | 9m47s |
| 14 | [M23] | math-medium | verified | 4m16s |
| 15 | [M26] | math-hard | verified | 4m |
| 16 | ▶ [M22] | math-medium | verified | 3m29s |
| 17 | [M32] | math-hard | verified | 3m17s |
| 18 | ▶ [**] | verified | 6m10s | |
| 19 | [M39] | math-project | verified | 8m36s |
| 20 | [M40] | math-project | solved | 3m34s |
| 21 | [M25] | math-medium | verified | 5m24s |
| 22 | [M23] | math-medium | verified | 2m05s |
| 23 | [M22] | math-medium | solved | 4m57s |
| 24 | [M27] | math-hard | verified | 9m28s |
| 25 | [M47] | math-research | verified | 4m57s |
| 26 | ▶ [M26] | math-hard | verified | 9m57s |
TAOCP 4.6.1 Exercise 1
Let u(x)=x^6+x^5-x^4+2x^3+3x^2-x+2, and
TAOCP 4.6.1 Exercise 2
Let f(x) = 3x^6 + x^5 + 4x^4 + 3x^3 + 4x + 3 and let its reverse be
TAOCP 4.6.1 Exercise 3
Let $S$ be a field, and let $u(x),v(x)\in S[x]$.
TAOCP 4.6.1 Exercise 4
Let $d_0=m,\qquad d_1=n,\qquad d_2=n_1,\qquad \ldots,\qquad d_{t+1}=n_t,\qquad d_{t+2}=-\infty,$ be the sequence of degrees occurring in Euclid's algorithm modulo $p$.
TAOCP 4.6.1 Exercise 5
Let $P_n=\Pr\bigl(\gcd(u(x),v(x))=1\bigr),$ where $u(x)$ and $v(x)$ are independently and uniformly distributed monic polynomials of degree $n$ over the field $\mathbf F_p$.
TAOCP 4.6.1 Exercise 6
**Exercise 4.
TAOCP 4.6.1 Exercise 7
Let $S$ be a unique factorization domain, and let $f(x)\in S[x]$ be a unit.
TAOCP 4.6.1 Exercise 8
Let $f(x)$ be a polynomial with integer coefficients.
TAOCP 4.6.1 Exercise 9
Let $S$ be a unique factorization domain, and let $u(z),v(z)\in S[z]$ be primitive polynomials.
TAOCP 4.6.1 Exercise 10
Let $S$ be a unique factorization domain.
TAOCP 4.6.1 Exercise 11
Table 1 in Section 4.
TAOCP 4.6.1 Exercise 12
Let $u(x)$ and $v(x)$ be polynomials over a field $S$, with $\deg(u) = m$ and $\deg(v) = n$, and let $u_1(x), u_2(x), \ldots$ be the sequence of polynomials obtained during a run of Algorithm C (the E...
TAOCP 4.6.1 Exercise 13
Let $S$ be a unique factorization domain, and let $u(x),v(x)\in S[x]$.
TAOCP 4.6.1 Exercise 14
Let u(x)=u_mx^m+\cdots,\qquad v(x)=ax^n+\cdots, where $a=l(v)$, and let $m=\deg(u)$, $n=\deg(v)$.
TAOCP 4.6.1 Exercise 15
We are asked to prove Hadamard's inequality, equation (25) in Section 4.
TAOCP 4.6.1 Exercise 16
Let N(S_1,\ldots,S_n) = |S_1|\cdots |S_n| -
TAOCP 4.6.1 Exercise 17
Let $\mathcal F=\mathbb Q\langle A\rangle$ denote the free associative algebra generated by the alphabet $A$ over the rationals.
TAOCP 4.6.1 Exercise 18
**Solution.
TAOCP 4.6.1 Exercise 19
Let L(A,B)=\{\,XA+YB : X,Y\in M_n(\mathbb Z)\,\}.
TAOCP 4.6.1 Exercise 20
The exercise asks for an investigation rather than a theorem with a single conclusion.
TAOCP 4.6.1 Exercise 21
Let the input polynomials be u_0(x),\qquad u_1(x), with
TAOCP 4.6.1 Exercise 22
Let $f_0(x),f_1(x),\ldots,f_m(x)$ be the Sturm sequence associated with a squarefree polynomial $f_0(x)$, defined by $f_{i-1}(x)=q_i(x)f_i(x)-f_{i+1}(x)\qquad(1\le i<m),$ where $f_m(x)$ is a nonzero c...
TAOCP 4.6.1 Exercise 23
Let $u(x),v(x)\in\mathbf{R}[x]$ be polynomials whose coefficients are represented in floating-point arithmetic.
TAOCP 4.6.1 Exercise 24
A fully corrected solution cannot be written from the information provided.