TAOCP 4.5.2: The Greatest Common Divisor
Section 4.5.2 exercises: 42/42 solved.
Section 4.5.2. The Greatest Common Divisor
Exercises from TAOCP Volume 2 Section 4.5.2: 42/42 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M21] | math-medium | verified | 3m04s |
| 2 | [M22] | math-medium | verified | 1m15s |
| 3 | [M23] | math-medium | verified | 1m15s |
| 4 | [M21] | math-medium | verified | 4m02s |
| 5 | ▶ [M26] | math-hard | solved | 3m42s |
| 6 | [M22] | math-medium | verified | 4m59s |
| 7 | [M20] | math-medium | verified | 2m35s |
| 8 | ▶ [M28] | math-hard | verified | 3m34s |
| 9 | [18] | medium | verified | 3m |
| 10 | ▶ [**] | verified | 2m28s | |
| 11 | [**] | verified | 1m19s | |
| 12 | [**] | verified | 1m07s | |
| 13 | [**] | verified | 1m11s | |
| 14 | ▶ [**] | verified | 1m19s | |
| 15 | [**] | verified | 2m18s | |
| 16 | [**] | verified | 1m05s | |
| 17 | ▶ [**] | solved | 4m28s | |
| 18 | [**] | verified | 56s | |
| 19 | [**] | verified | 1m11s | |
| 20 | [**] | verified | 2m18s | |
| 21 | [**] | solved | 4m | |
| 22 | [**] | verified | 2m39s | |
| 23 | ▶ [**] | verified | 2m21s | |
| 24 | [**] | solved | 3m11s | |
| 25 | [**] | solved | 4m13s | |
| 26 | [**] | solved | 4m08s | |
| 27 | [**] | verified | 1m24s | |
| 28 | [**] | verified | 1m14s | |
| 29 | ▶ [**] | solved | 2m09s | |
| 30 | [**] | verified | 2m03s | |
| 31 | [**] | verified | 2m12s | |
| 32 | [**] | solved | 2m10s | |
| 33 | [**] | verified | 13m02s | |
| 34 | [**] | verified | 2m42s | |
| 35 | [**] | solved | 3m33s | |
| 36 | ▶ [**] | solved | 7m27s | |
| 37 | [**] | verified | 6m17s | |
| 38 | ▶ [**] | verified | 5m02s | |
| 39 | ▶ [M28] | math-hard | verified | 1m12s |
| 40 | ▶ [M25] | math-medium | verified | 26m23s |
| 41 | [M22] | math-medium | verified | 23m47s |
| 42 | [M30] | math-hard | verified | 17m06s |
TAOCP 4.5.2 Exercise 1
We derive equations (8) through (12) from the prime-factor definitions (6) and (7).
TAOCP 4.5.2 Exercise 2
Let u=\prod_{p} p^{u_p}, \qquad v_i=\prod_{p} p^{v_{i,p}} \quad (1\le i\le n)
TAOCP 4.5.2 Exercise 3
Let n=\prod_{p}p^{a_p} be the canonical factorization of $n$, as in (5), where only finitely many exponents $a_p$ are nonzero.
TAOCP 4.5.2 Exercise 4
Let $u$ and $v$ be positive integers.
TAOCP 4.5.2 Exercise 5
Exercise 4.
TAOCP 4.5.2 Exercise 6
Let $u$ and $v$ be random positive integers.
TAOCP 4.5.2 Exercise 7
In Program B of §4.
TAOCP 4.5.2 Exercise 8
Let the notation be that of Knuth's analysis of Program B.
TAOCP 4.5.2 Exercise 9
We are asked to compute $\gcd(31408, 2718)$ using **Algorithm B**, and then to find integers $m$ and $n$ such that $31408 \, m + 2718 \, n = \gcd(31408, 2718)$ using **Algorithm X**.
TAOCP 4.5.2 Exercise 10
Let $q_n$ denote the number of ordered pairs $(u,v)$ with $1 \le u,v \le n$ such that $\gcd(u,v) = 1$.
TAOCP 4.5.2 Exercise 11
By Theorem 4.
TAOCP 4.5.2 Exercise 12
If $u$ and $v$ are random positive integers, let $d$ be a positive integer.
TAOCP 4.5.2 Exercise 13
Let P_d=\Pr(\gcd(u,v)=d).
TAOCP 4.5.2 Exercise 14
Let G=\gcd(u,v).
TAOCP 4.5.2 Exercise 15
We are asked to determine the terminal values of $v_1$ and $v_2$ in **Algorithm X** from Section 4.
TAOCP 4.5.2 Exercise 16
Since $v \perp m$, the extended Euclidean algorithm yields integers $a$ and $b$ such that $av+bm=1.$ Reducing modulo $m$ gives $av\equiv 1 \pmod m,$ so $a$ is the multiplicative inverse of $v$ modulo...
TAOCP 4.5.2 Exercise 17
**Exercise 4.
TAOCP 4.5.2 Exercise 18
Algorithm L already performs several Euclidean divisions at once by using the leading digits of $u$ and $v$.
TAOCP 4.5.2 Exercise 19
For part (a), consider the system 3x + 7y + 11z = 1, \quad 5x - 7y - 3z = 3.
TAOCP 4.5.2 Exercise 20
Let $M=2^{n'-1}.$ The odd integers in the interval $2^{n'}\le u,v<2^{n'+1}$ are $u=2^{n'}+(2a+1),\qquad v=2^{n'}+(2b+1),$ with $0\le a,b<M$.
TAOCP 4.5.2 Exercise 21
We are asked to analyze the asymptotic behavior of the average number of subtraction steps $C_{mn}$ and shift steps $D_{mn}$ in **Algorithm B**, when $u$ and $v$ are odd integers with \lfloor \lg u \r...
TAOCP 4.5.2 Exercise 22
**Exercise 4.
TAOCP 4.5.2 Exercise 23
Let F_n(x)=\Pr\!
TAOCP 4.5.2 Exercise 24
The proposed solution is mathematically correct as far as it goes, but it does not answer the exercise that Knuth intended.
TAOCP 4.5.2 Exercise 25
**Exercise 4.
TAOCP 4.5.2 Exercise 26
We are asked to prove that, for a function $G(x)$ satisfying (36)–(40), 2G(x) - 5G(2x) + 2G(4x) = G(1+2x) - 2G(1+4x) + 2G(1 + 1/x) - G(1 + 1/(2x)).
TAOCP 4.5.2 Exercise 27
Let $\psi_n$ be defined by the logarithmic generating function that precedes (58): \log\frac{x}{e^x-1}=\sum_{n\ge1}\psi_n x^n .
TAOCP 4.5.2 Exercise 28
Equation (58) expresses $\psi_n$ as a constant multiple of the Bernoulli number $B_{2n}$.
TAOCP 4.5.2 Exercise 29
After the first subtract-and-shift cycle of Algorithm B, the ratio $x = \min(u, v)/\max(u, v)$ is transformed according to the rule $x \mapsto x/(1 + 2^k x)$, where $k$ is the number of trailing zeros...
TAOCP 4.5.2 Exercise 30
**Corrected Solution for Exercise 4.
TAOCP 4.5.2 Exercise 31
**Exercise 4.
TAOCP 4.5.2 Exercise 32
No.
TAOCP 4.5.2 Exercise 33
Let $T(u,v)$ denote the number of iterations performed by Harris's binary Euclidean algorithm after the common factor $2^{\min(\nu_2(u),\nu_2(v))}$ has been removed.
TAOCP 4.5.2 Exercise 34
The exercise asks for a rigorous justification of Brent's probabilistic model.
TAOCP 4.5.2 Exercise 35
**Exercise 4.
TAOCP 4.5.2 Exercise 36
Let B(u,v) denote the number of subtraction steps performed by Algorithm B.
TAOCP 4.5.2 Exercise 37
**Problem.
TAOCP 4.5.2 Exercise 38
Algorithm B is the binary gcd algorithm.
TAOCP 4.5.2 Exercise 39
Algorithm B is the binary gcd algorithm.
TAOCP 4.5.2 Exercise 40
Let M=\max(|u|,|v|), where $u$ is initially odd.
TAOCP 4.5.2 Exercise 41
Let G(m,n)=\gcd(10^m-1,\;10^n-1), where $m,n\ge 0$.
TAOCP 4.5.2 Exercise 42
We are asked to evaluate the determinant D_n = \begin{vmatrix} \gcd(1,1) & \gcd(1,2) & \cdots & \gcd(1,n) \\ \gcd(2,1) & \gcd(2,2) & \cdots & \gcd(2,n) \\ \vdots & & & \vdots \\