TAOCP 4.6.2: Factorization of Polynomials
Section 4.6.2 exercises: 34/40 solved.
Section 4.6.2. Factorization of Polynomials
Exercises from TAOCP Volume 2 Section 4.6.2: 34/40 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | ▶ [M25] | math-medium | solved | 4m39s |
| 2 | ▶ [M25] | math-medium | verified | 3m |
| 3 | [M25] | math-medium | verified | 4m18s |
| 4 | [HM28] | hm-hard | solved | 2m47s |
| 5 | [HM28] | hm-hard | verified | 9m16s |
| 6 | [M21] | math-medium | verified | 3m35s |
| 7 | [M22] | math-medium | - | - |
| 8 | [HM20] | hm-medium | verified | 2m23s |
| 9 | [20] | medium | solved | 7m54s |
| 10 | ▶ [21] | medium | solved | 11m22s |
| 11 | [22] | medium | - | - |
| 12 | ▶ [M22] | math-medium | - | - |
| 13 | [M25] | math-medium | solved | 10m01s |
| 14 | [M35] | math-hard | - | - |
| 15 | ▶ [M27] | math-hard | solved | 2m38s |
| 16 | [M30] | math-hard | solved | 2m45s |
| 17 | [M23] | math-medium | verified | 2m12s |
| 18 | ▶ [M25] | math-medium | solved | 2m50s |
| 19 | [M20] | math-medium | verified | 1m08s |
| 20 | [HM33] | hm-hard | solved | 6m58s |
| 21 | [HM33] | hm-hard | - | - |
| 22 | ▶ [M24] | math-medium | verified | 4m46s |
| 23 | [**] | - | - | |
| 24 | [**] | verified | 5m12s | |
| 25 | [**] | solved | 8m25s | |
| 26 | [**] | verified | 4m05s | |
| 27 | [**] | verified | 3m45s | |
| 28 | [**] | verified | 2m08s | |
| 29 | [**] | verified | 2m38s | |
| 30 | [**] | verified | 4m24s | |
| 31 | [**] | verified | 5m17s | |
| 32 | ▶ [**] | solved | 10m42s | |
| 33 | [M18] | math-medium | verified | 1m20s |
| 34 | ▶ [M25] | math-medium | verified | 3m09s |
| 35 | [M22] | math-medium | verified | 2m53s |
| 36 | [M22] | math-medium | verified | 2m33s |
| 37 | [HM24] | hm-medium | verified | 2m33s |
| 38 | [HM27] | hm-hard | verified | 2m20s |
| 39 | [HM42] | hm-project | solved | 9m40s |
| 40 | ▶ [M20] | math-medium | verified | 6m28s |
TAOCP 4.6.2 Exercise 1
The proposed solution does not answer the exercise that was asked.
TAOCP 4.6.2 Exercise 2
(a) Let $R$ be a unique factorization domain (UFD), and let $u(x) \in R[x]$ be monic.
TAOCP 4.6.2 Exercise 3
Let U(x)=u_1(x)u_2(x)\cdots u_r(x), where the polynomials $u_1,\ldots,u_r$ are pairwise relatively prime over the field $S$.
TAOCP 4.6.2 Exercise 4
Let $p$ be a prime number, and let $a_{n,p}$ denote the number of monic irreducible polynomials of degree $n$ over the finite field $\mathbb{F}_p$.
TAOCP 4.6.2 Exercise 5
Let A_{n,p}=\sum_{m=1}^n \frac{a_{m,p}}{p^m}, where $a_{m,p}$ denotes the number of monic irreducible polynomials of degree $m$ over $\mathbf F_p$.
TAOCP 4.6.2 Exercise 6
We are asked to prove the congruence x^p - x \equiv (x-0)(x-1)\cdots(x-(p-1)) \pmod{p}, \eqno(9) where $p$ is a prime and arithmetic is in the field $\mathbb{F}_p$ of $p$ elements.
TAOCP 4.6.2 Exercise 8
Algorithm N triangularizes the matrix $Q-I$ by means of elementary column operations.
TAOCP 4.6.2 Exercise 9
Since $2$ is a primitive root modulo $101$, every nonzero residue modulo $101$ is of the form 2^k \pmod{101}, \qquad 0\le k\le 99.
TAOCP 4.6.2 Exercise 10
The exercise asks for the complete factorization of the polynomial $u(x)$ in equation (22) by Berlekamp's method.
TAOCP 4.6.2 Exercise 13
We are asked to give an explicit factorization of x^8 + 1 modulo an odd prime $p$, using the quantities $\sqrt{-1}, \sqrt{2}, \sqrt{-2}$ whenever these exist in $\mathbb{F}_p$.
TAOCP 4.6.2 Exercise 15
Given a prime $p$ and an integer $u$ for which a square root modulo $p$ is known to exist, we seek an efficient algorithm for finding an integer $v$ satisfying v^2 \equiv u \pmod p.
TAOCP 4.6.2 Exercise 16
Let $p$ be a prime, and let $f(x)$ be an irreducible polynomial modulo $p$ of degree $n$.
TAOCP 4.6.2 Exercise 17
Let $F$ be a finite field with $13^2 = 169$ elements.
TAOCP 4.6.2 Exercise 18
Let $u(x) = u_n x^n + u_{n-1} x^{n-1} + \cdots + u_0$ be a primitive polynomial with integer coefficients, so that $\gcd(u_0, u_1, \ldots, u_n) = 1$, and define the monic polynomial $v(x) = u_n^{-1} \...
TAOCP 4.6.2 Exercise 19
Assume that $u(x)$ is reducible over the integers.
TAOCP 4.6.2 Exercise 20
Let u(x)=u_nx^n+\cdots+u_0 =u_n\prod_{r=1}^{n}(x-\alpha_r), and define
TAOCP 4.6.2 Exercise 22
Assume that for some $r \ge 1$ we are given polynomials u(x),\ v_s(x),\ w_s(x),\ \alpha(x),\ \beta(x)\in\mathbb Z[x] such that
TAOCP 4.6.2 Exercise 24
**Solution.
TAOCP 4.6.2 Exercise 25
Error in message stream
TAOCP 4.6.2 Exercise 26
Let $u(x)=p_1(x)^{e_1}\cdots p_r(x)^{e_r}$ be the factorization of $u(x)$ modulo $p$, and let $d_j=\deg p_j(x)$ for $1\le j\le r$, with multiplicities included.
TAOCP 4.6.2 Exercise 27
Fix a degree $n \ge 1$.
TAOCP 4.6.2 Exercise 28
Let $N_d$ denote the number of monic irreducible polynomials of degree $d$ over $\mathbb{F}_p$.
TAOCP 4.6.2 Exercise 29
Let g(x)=p_1(x)p_2(x)\cdots p_r(x), where the $p_j(x)$ are distinct irreducible polynomials of degree $d$, and let $q=p^d$.
TAOCP 4.6.2 Exercise 30
Let $T(t)=t(x)+t(x)^p+t(x)^{p^2}+\cdots+t(x)^{p^{d-1}}.$ Since $q(x)$ is irreducible of degree $d$, the residue class ring modulo $q(x)$ is the finite field with $p^d$ elements.
TAOCP 4.6.2 Exercise 31
**Exercise 4.
TAOCP 4.6.2 Exercise 32
**Exercise 4.
TAOCP 4.6.2 Exercise 33
The statement is false.
TAOCP 4.6.2 Exercise 34
Let $u(x)$ be a primitive polynomial over the integers, and suppose that the unique factorization of $u(x)$ in a UFD is $u(x) = \prod_{i \ge 1} \prod_{j=1}^{r_i} p_{i,j}(x)^i,$ where $p_{i,j}(x)$ are...
TAOCP 4.6.2 Exercise 35
Let u(x)=u_1(x)u_2(x)^2u_3(x)^3\cdots u_e(x)^e, where the $u_i(x)$ are squarefree and pairwise relatively prime, and where $u_e(x)\ne1$.
TAOCP 4.6.2 Exercise 36
Let u(x)=\prod_{i\ge1} u_i(x)^i be the squarefree representation of the given polynomial modulo $p$.
TAOCP 4.6.2 Exercise 37
Consider a random monic polynomial $u(x)$ of degree $n$ with coefficients chosen uniformly from ${0,1,\ldots,p-1}$.
TAOCP 4.6.2 Exercise 38
Let u(x)=x^n+u_{n-1}x^{n-1}+\cdots+u_1x+u_0, \qquad u_0\ne0, with integer coefficients.