Chapter 31

Exercise 31.1-1

We can write $c=\lfloor c/a\rfloor a+b=\lfloor (a+b)/a\rfloor a+b=1\cdot a+b$ and it follows from the Division theorem that $b$ is the remainder of dividing $c$ by $a$.

Exercise 31.1-2

You can read the proof here.

Exercise 31.1-3

We have $a|b \implies b=pa$ and $b|c\implies c=qb$ for integers $p$ and $q$. Therefore, $c=(pq)a\implies a|c$.

Exercise 31.1-4

The only divisors of $p$ are 1 and $p$. No divisor of $k$ except 1 divides $p$, since $k<p \implies p \nmid k$. Therefore, $\gcd⁡(k, p)=1$.

Exercise 31.1-5

We start from the fact that $\gcd(a,n)=1$, so we get

$$\begin{align*} 1 &= ax+ny && \text{(by Theorem (3.12))} \\ b &= abx +nby && \text{(after multiplying both sides by } b \text{)} \\ b &= nkx+nby && \text{(} n|ab \implies ab=kn \text{)} \\ b &= n(kx+by) \\ &\therefore n|b \end{align*}$$

Exercise 31.1-6

Lemma 1

For any integers $a_1,a_2,\dots,a_n$, and $p$, if $\gcd(a_i,p)=1$ for all $i=1,2,\dots,n$, then $\gcd(\prod_{i=1}^n a_i,p)=1$.

Proof We prove the lemma by induction on $n$. The base cases are when $n=1 \lor n=2$ and both trivially hold (see Theorem 31.6). For $n>2$ we have

$$\begin{align*} \gcd(a_i, p) &=1 && \text{(for all } i=1,2,\dots,n \text{)} \\ &\implies \gcd(\prod_{i=1}^{n-1}a_i, p)=1 \land \gcd(a_n,p)=1 && \text{(by the inductive hypothesis)} \\ &\implies \gcd(\prod_{i=1}^na_i, p)=1 && \text{(by Theorem (3.16))} \end{align*}$$

According to the principles of mathematical induction, we can conclude that the lemma holds for all $n \ge 1$. Q.E.D.

$\binom{p}{k}=\frac{p!}{k!(p-k)!}$ is a positive integer, as it represents the number of ways to select $k$ items out of $p$. Based on Exercise 31.1-4 and Lemma 1, for $0<k<p$, $\gcd(k!,p)=1$ and $\gcd((p-k)!,p)=1$, so $\binom{p}{k}=\big(\frac{(p-1)!}{k!(p-k)!}\big)p \implies p|\binom{p}{k}$. Thus, in a binomial expansion all terms except the first and last one are divisible by $p$, which concludes the proof.

Exercise 31.1-7

We successively apply the Division theorem, so we have

$$\begin{align*} x &= q'b + (x \!\!\!\!\mod b) \\ &= q'ka + (x \!\!\!\!\mod b) && \text{(} a|b \implies b=ka \text{)} \\ &= q'ka + q''a + ((x \!\!\!\!\mod b) \!\!\!\!\mod a) \\ &= (q'k+q'')a+((x \!\!\!\!\mod b) \!\!\!\!\mod a) \\ &\therefore (x \!\!\!\!\mod b) \!\!\!\!\mod a = x \!\!\!\!\mod a \end{align*}$$

For the second part we get

$$\begin{align*} x \!\!\!\!\mod a &= (x \!\!\!\!\mod b) \!\!\!\!\mod a && \text{(by the first part)} \\ &= (y\!\!\!\! \mod b) \!\!\!\!\mod a && \text{(since } x = y \space(\!\!\!\!\!\!\mod b) \text{)} \\ &= y\!\!\!\! \mod a && \text{(by the first part)} \end{align*}$$

Exercise 31.1-8

Assume that multiplication of two $\beta$-bit integers requires $O(\beta^2)$ time and equality test of two $\beta$-bit integers requires $O(\beta)$ time. The algorithm below only showcases an existence of a solution in time polynomial in $\beta$ without claiming anything about its asymptotic optimality. As a matter of fact, it is far from being optimal.

The smallest candidate is $a=2$ and $2^\beta>n \implies k \in [2,\beta)$. Therefore, we iterate over all possible exponents $k$ in increasing order and see if the $k$th root of $n$ is an integer.

We can leverage binary search over the interval $[2,n)$ in searching for this root. We iteratively raise each candidate $a$ to the $k$th power by multiplying the current product with $a$ (initially setting it to 1). In each iteration, we also check if this product is greater than $n$, so that we stop as soon as possible. This stage demands $O(\beta)(O(\beta^2)+O(\beta))=O(\beta^3)$ time. In case of a match, we finish the search, otherwise, recurse into the lower or upper subinterval depending on whether $a^k>n$ or not, respectively. If the subinterval becomes empty, then we declare an unsuccessful attempt to find the root for the given exponent.

All in all, we can determine whether a given $\beta$-bit integer $n$ is a nontrivial power in $O(\beta^5)$ time.

Exercise 31.1-9

Proof of 31.6

By definition, $\gcd(a,b)$ is the largest element in the set $D_{(a,b)}$ of the common divisors of $a$ and $b$. Analogously, $\gcd(b,a)$ is the largest element in the set $D_{(b,a)}$ of the common divisors of $b$ and $a$. We know that $D_{(a,b)}=D_{(b,a)}$ and there cannot be two different largest element in a set. Therefore, $\gcd(a,b) = \gcd(b,a)$.

Proof of 31.7

$d_1=\gcd(a,b) \implies (d_1|a \land d_1|b)$, but this also means that $d_1|(-a)$, hence $d_1 \le d_2=\gcd(-a,b)$. With similar reasoning we can conclude that $d_2 \le d_1$, therefore $d_1=d_2$.

Proof of 31.8

$$\begin{align*} \gcd⁡(a,b)&=\gcd⁡(−a,b) && \text{(by property (31.7))} \\ &=\gcd⁡(b,−a) && \text{(by property (31.6))} \\ &=\gcd⁡(−b,−a) && \text{(by property (31.7))} \\ &\therefore \gcd⁡(a,b)=\gcd⁡(|a|,|b|) \end{align*}$$

Proof of 31.9

By property (31.8) we have that $\gcd⁡(a,0)=\gcd⁡(|a|,0)$. Any common divisor of $|a|$ and 0 cannot be larger than $|a|$, so $\gcd⁡(a,0)=|a|$, since any integer divides 0.

Proof of 31.10

By property (31.8) we have that $\gcd⁡(a,ka)=\gcd⁡(|a|,|ka|)=\gcd⁡(|a|,|k||a|)$. We have the following cases:

• If $a=0$ then $\gcd⁡(0,0)=|a|$.

• If $k=0$ then $\gcd⁡(a,0)=|a|$ by property (31.9).

• Let $a \neq 0 \land k \neq 0$. We have that $|a|≤|k||a|$ when $|k|>0$. Furthermore, $a \neq 0 \implies |a|\ge 1$. Therefore, $\gcd⁡(|a|,|k||a|) =\min⁡\{|a|,|k||a|\} = |a|$.

Exercise 31.1-10

Let $d_1=\gcd(a,\gcd(b,c))$ and $d_2=\gcd(\gcd(a,b),c)$. We prove the statement from the book by showing that $d_1|d_2$ and $d_2|d_1$, thus by equation (31.5) they must be equal, as both of them are nonnegative.

We know that $d_1|a \land d_1|\gcd(b,c)$, which entails that $d_1|b \land d_1|c$. The fact that $d_1$ divides both $a$ and $b$ implies that it also divides $\gcd(a,b)$ by Corollary 31.3. Therefore, $d_1|d_2$ by applying again Corollary 31.3.

Using the same reasoning we can conclude that $d_2|d_1$, which finishes the proof about associativity of the $\gcd$ operator.

Exercise 31.1-11

You can read the proof here that uses only facts mentioned in the book.

Exercise 31.1-12

The $O(\beta^2)$ time algorithm shown here also handles the edge case when a divisor is larger than a number to be divided.

Exercise 31.1-13

We follow the hint from the book. The main idea is to split a $\beta$-bit binary number and obtain the top and bottom halves of the result with separate recursions. The divide step must enable an easy assembly of these partial results. Since we are converting into a decimal representation it makes sense to split according to powers of 10. The key insight is to precompute these powers (in binary) to facilitate efficient splitting.

Precomputing powers of 10

Precomputation is a powerful technique in algorithm design. The steps to accomplish this are laid out below:

1

Configure parameters

Calculate the total number of decimal digits $D=\lceil\beta \lg_{10}2\rceil$, set the recursion depth $L=\lceil\lg D\rceil$, and create 1-indexed lookup tables $S$ (stores split points) and $P$ (stores powers of 10) as static arrays of size $L$.

2

Fill the lookup tables

For each level $i=1,2,\dots,L$:

1. Determine the split point $S_i=\lceil D/2^i \rceil$ (half the digits at level $i$).

2. Compute $P_i=10^{S_i}$ using exponentiation by squaring.

Each $P_i$ has $\Theta(\beta/2^i)$ bits, so computing it demands $O(M(\beta /2^i)\lg \beta)$ time. The total time is $\sum_{i=1}^L {O(M(\beta /2^i)\lg \beta)}=O(\sum_{i=1}^L {M(\beta /2^i)\lg \beta)}=O(M(\beta)\lg \beta)$ using the fact that $M(\beta)=\Omega(\beta)$ and assuming $M$ satisfies the properties of standard multiplication algorithms, like, being non-decreasing as well as the sum of $M$ over geometrically decreasing sizes is dominated by $M(\beta)$ (sort of weak regularity).

Recursive conversion function

Assume that handling decimal representation is not influencing the asymptotical behavior of our main routine. For example, concatenating two decimal representations is expected to run in $O(1)$ time.

1

Function signature

Our function has the signature $Convert(n, d, i)$, where

• $n$ is the number to convert

• $d$ is the upper bound on number of decimal digits of $n$

• $i$ is the current recursion level

The function returns a decimal representation of $n$. It should be initially called with $Convert(N, D, 1)$.

2

Base case

If $d=1$ then return the single digit representation of $n$.

3

Recursive case

1. Compute the values for the top $t=\lfloor n /P_i \rfloor$ and bottom $b=n \!\!\mod P_i$ halves.

2. Recursively obtain the decimal representation of the top half $r_{top}=Convert(t,d-S_i,i+1)$.

3. Recursively obtain the decimal representation of the bottom half $r_{bottom}=Convert(b,S_i,i+1)$.

4. Pad $r_{bottom}$ with leading zeros to length $S_i$.

5. Produce a combined result $r=r_{top} \Join r_{bottom}$ by concatenating the two halves.

6. Remove leading zeros from $r$, if any.

7. Return $r$.

The recurrence formula is $T(\beta)=2T(\beta/2)+M(\beta)$. We have two variations on the recurrence using the fact that $M(\beta)=\Omega(\beta)$:

• If $M(\beta)=\Theta(\beta\lg \beta)$ then by the Master theorem $T(\beta)=\Theta(M(\beta)\lg \beta)$.

• If $M(\beta)=\Omega(\beta^{1+\epsilon})$ for some $\epsilon>0$ then by the Master theorem $T(\beta)=\Theta(M(\beta))$ assuming $M(\beta)$ satisfies the regularity condition (most standard multiplication/division algorithms do).

We can conclude that $T(\beta)=O(M(\beta)\lg \beta)$ taking into account the precomputation and conversion times.

Exercise 31.1-14

See the answer here with a derailed solution.

Exercise 31.2-1

You can read a very nice proof in the attached PDF document. It was retrieved on July, 2025 from this link. There are two remarks about external references in the content:

• Proposition 1(iv) is about the rule $(a \neq 0 \land d|a) \implies |d| \le |a|$. In essence, you can also use equation (31.5), in the context of the paper, instead of the previously mentioned proposition.

• Proposition 1(i) is Exercise 31.1-3.

131KB

gcd-with-fta.pdf

pdf

Exercise 31.2-2

We create a table, similar to Figure 31.1 from the book, by running the next Python 3 script.

rows = []

def add_row(a, b, d, x, y):
    rows.append(f"{a}\t{b}\t{a // b if b > 0 else '-'}\t{d}\t{x}\t{y}")

def print_rows():
    for row in reversed(rows):
        print(row)

def extended_euclid(a, b):
    if b == 0:
        add_row(a, b, a, 1, 0)
        return (a, 1, 0)
    
    (d, x, y) = extended_euclid(b, a % b)
    (x, y) = (y, x - (a // b) * y)
    add_row(a, b, d, x, y)
    return (d, x, y)

extended_euclid(899, 493)
print("a\tb\t⌊a/b⌋\td\tx\ty\n")
print_rows()

Observe the usage of the list rows to reverse the output shown below.

a	b	⌊a/b⌋	d	x	y

899	493	1	29	-6	11
493	406	1	29	5	-6
406	87	4	29	-1	5
87	58	1	29	1	-1
58	29	2	29	0	1
29	0	-	29	1	0

Exercise 31.2-3

Let $d_1=\gcd(a,n)$ and $d_2=\gcd(a+kn,n)$. We proceed by showing that $d_1|d_2$ and $d_2|d_1$, thus according to equation (31.5) they are equal.

We know that $d_1|a$ and $d_1|n$, so by equation (31.4) we have $d_1|a+kn$. Based on Corollary 31.3 we can conclude that $d_1|d_2$.

We know that $d_2|n$, so $n=pd_2$ for some integer $p$. Furthermore, $d_2|a+kn$, thus $a+kn=qd_2$ for some integer $q$. Therefore, $a=qd_2-kn=qd_2-kpd_2=(q-kp)d_2$ that implies $d_2|a$. Based on Corollary 31.3 we can conclude that $d_2|d_1$.

$a=1\space(\!\!\!\!\mod n) \implies a=1+kn$, so $\gcd(1+kn,n)=\gcd(1,n)$ by equation (31.18). Consequently, we have $\gcd(a,n)=1$.

Exercise 31.2-4

Below is the iterative version of Euclid's algorithm in Python 3.

def iterative_euclid(a, b):
    while b > 0:
        a, b = b, a % b
    return a

Exercise 31.2-5

According to Lamé’s theorem if $k=2+\log_{\phi} b$ and $b<F_{k+1} \approx \frac {\phi^{k+1}}{\sqrt {5}}=\frac{\phi^3}{\sqrt {5}}b$, which definitely holds, then the call $Euclid(a, b)$ will make fewer than $k$ recursive calls.

Let $d=\gcd(a,b)$, so $a=d\cdot (a/d)$ and $b=d\cdot (b/d)$. According to Corollary 31.4 we have $\gcd(a,b)=\gcd(d\cdot (a/d),d\cdot (b/d))=d\gcd(a/d,b/d)$. Therefore, if $k=2+\log_{\phi} {(b/d)}$ and $b/d<F_{k+1} \iff b<dF_{k+1}$, which again defintely holds, then the call $Euclid(a, b)$ will make fewer than $k$ recursive calls.

Exercise 31.2-6

Assume that $k>2$, otherwise we would immediately reach the base case. $F_{k+1}=F_k+F_{k-1}$, hence by Exercise 31.1-1 we have that $F_{k-1}=F_{k+1} \!\!\mod F_k$. According to the properties of Fibonacci numbers $F_{k+1}>F_k$ for all $k\ge2$. Therefore, the call to $Extended\text{\textendash}Euclid(F_{k+1},F_k)$ recurses into $Extended\text{\textendash}Euclid(F_k,F_{k-1})$, and this process continues until hitting the base that happens right after the call to $Extended\text{\textendash}Euclid(F_3,F_2)$ . The final call $Extended\text{\textendash}Euclid(F_2,0)$ returns a 3-tuple $(1,1,0)$. Thus, $\gcd(F_{k+1},F_k)=1$. We now need to find out the coefficients $x$ and $y$.

In general, $Extended\text{\textendash}Euclid(F_{k+1},F_k)$ returns a 3-tuple $(1,(-1)^{k+1}F_{k-2},(-1)^kF_{k-1})$. We prove this by induction on $k$. The base case $k=2$ obviously holds.

For $k>2$ the quotient $q=\lfloor F_{k+1}/F_k \rfloor=\lfloor (F_k+F_{k-1})/F_k \rfloor=1$. Thus, $(d,x,y)=(d',y',x'-y')$ at all levels. By the inductive hypothesis the call to $Extended\text{\textendash}Euclid(F_k,F_{k-1})$ returns a 3-tuple $(1,(-1)^kF_{k-3},(-1)^{k-1}F_{k-2})$, thus $Extended\text{\textendash}Euclid(F_{k+1},F_k)$ returns

$$\begin{align*} (1,(-1)^{k-1}F_{k-2},(-1)^kF_{k-3}-(-1)^{k-1}F_{k-2}) &= (1,(-1)^{k+1}F_{k-2},(-1)^kF_{k-3}+(-1)^kF_{k-2}) \\ &= (1,(-1)^{k+1}F_{k-2},(-1)^k(F_{k-3}+F_{k-2}) \\ &= (1,(-1)^{k+1}F_{k-2},(-1)^kF_{k-1}) \quad \checkmark \end{align*}$$

Observe in line 1 that $(-1)^{k-1}=(-1)^{k+1}$.

Exercise 31.2-7

We proceed by induction on $n$. The base cases are when $n=1 \lor n=2$. If $n=1$ then we have nothing to permute and for $n=2$ we can apply equation (31.6) (see Exercise 31.1-9). For $n>2$ assume that the inductive hypothesis holds for $n$ arguments. Every permutation is consisted of individual pairwise swaps of elements. An informal indirect proof is an ability of any sorting algorithm to find the matching permutation that results in proper ordering of elements. This is attained in a step-by-step fashion, swapping each time a pair of elements on different positions. Thus, let us consider elements $a_i$ and $a_j$ where $0\le i <j \le n$. We have two cases:

1. If $i>0$ then it immediately follows by the inductive hypothesis that $\gcd⁡(a_0,a_1,\dots,a_i,\dots,a_j,\dots,a_n)=\gcd⁡(a_0,a_1,\dots,a_j,\dots,a_i,\dots,a_n)$.

2. If $i=0$ then we have the following sequence of equivalent transformations:

$$\begin{align*} \gcd⁡(a_i,a_1,\dots,a_j,\dots,a_n)&=\gcd⁡(a_i,\gcd(a_1,\dots,a_j,\dots,a_n)) \\ &= \gcd⁡(a_i,\gcd(a_j,a_1,\dots,a_n)) && \text{(by the inductive hypothesis)} \\ &= \gcd⁡(\gcd(a_j,a_1,\dots,a_n),a_i) && \text{(by equation (31.6))} \\ &= \gcd⁡(a_j,\gcd(a_1,\dots,a_n,a_i)) && \text{(by the associativity rule)} \\ &= \gcd⁡(a_j,\gcd(a_1,\dots,a_i,\dots,a_n)) && \text{(by the inductive hypothesis)} \\ &=\gcd⁡(a_j,a_1,\dots,a_i,\dots,a_n) \end{align*}$$

Exercise 31.1-10 proves that the $\gcd$ operator is associative. This property extends to arbitrary number of arguments due to the generalized associative law.

We can incrementally find the coefficients $x_0,x_1,\dots,x_n$ by using the extended Euclid's algorithm from the book. For efficiently updating the coefficients perform two passes over the array $X[0:n]$. Set $X[n]=1$. Store $X[i]=x_i$ from right to left and keep the multiplicative factors in a separate array $Y[0:n]$. Set $Y[0]=1$. In the second pass, iterate from left to right and multiply each $X[i]$ with the cumulative factor $\prod_{i=0}^i y_i$.

$$\begin{align*} \gcd⁡(a_0,a_1,\dots,a_n) &= \gcd⁡(a_0,\gcd⁡(a_1,\dots,a_n)) \\ &= xa_0+y\gcd⁡(a_1,a_2,\dots,a_n) \\ &=xa_0+y(x'a_1+y'\gcd⁡(a_2,a_3,\dots,a_n)) \\ &=xa_0+y(x'a_1+y'(x''a_2+y′′\gcd(a_3,a_4,\dots,a_n))) \\ &=\dots \end{align*}$$

In general, computing $\gcd(a,b)$ takes $O(\lg b)$ recursive calls, thus divisions. Even if $b > 0$ and $b|a$ it requires one division to hit the base case with a remainder of zero. Therefore, we definitely need at least $n$ divisions. If we also take into account the cost of finding coefficients, then we need to double this count.

Let $M=\max\{a_0,a_1,\dots,a_n\}$. The $\gcd$ function monotonically decreases as we add more nonzero arguments, i.e., $\gcd(a_{n-1},a_n)\ge\gcd(a_{n-2},a_{n-1},a_n)\ge\dots\ge \gcd⁡(a_0,a_1,\dots,a_n)$. This follows from the $\min$ function also being monotonically decreasing as we add more positive arguments and $\gcd⁡(a_0,a_1,\dots,a_n) \le \min\{|a_0|,|a_1|,\dots,|a_n|\}$. The worst-case scenario is when $\gcd$ turns out to be 1. Overall, there can be no more than $O(\lg M)$ divisions for a $\gcd$ to drop from a maximal possible value $M$ down to 1.

The total number of divisions performed by our algorithm is $O(n+\max\{a_0,a_1,\dots,a_n\})$.

Exercise 31.2-8

The base case is defined as $\text{lcm}(a,b)=\cfrac{|a\cdot b|}{\gcd(a,b)}$. The generalization to arbitrary number of arguments is the same as with the generic $\gcd$ introduced in Exercise 31.2-7. Therefore, we have

$$\text{lcm}(a_1,a_2,\dots,a_n)=\text{lcm}(a_1,\text{lcm}(a_2,a_3,\dots,a_n))$$

Exercise 31.2-9

We first describe the general case and demonstrate it using the example with $k=4$ from the book. WLOG assume that indices are 0-based.

1

Constructing the derived pairs

1. Write each index $i \in \{0,1,\dots,k-1\}$ into unique binary form using exactly $r=\lceil \lg k \rceil$ digits, padding with leading zeros, as needed.

2. For each bit position $0 \le j <r$ partition the set of input numbers into two groups:

   1. $A_j=\{n_i:\text{the }j\text{th bit from the right in the binary form of }i \text{ is }1\}$

   2. $B_j=\{n_i:\text{the }j\text{th bit from the right in the binary form of }i \text{ is }0\}$

3. For each $j$ produce $a_j=\prod_{n \in A_j} n$ and $b_j=\prod_{n \in B_j} n$, thus forming $r$ pairs $(a_j,b_j)$.

2

Proving correctness

If the set of input numbers are pairwise relatively prime, then $\gcd(n_s,n_t)=1$ for $s \neq t$. Fix any $j$. Suppose for the sake of contradiction that some prime $p|a_j$ and $p|b_j$. Consequently, there are some distinct numbers $n_s \in A_j$ and $n_t \in B_j$ such that $p|n_s$ and $p|n_t$. But that contradicts the initial assumption about our set of input numbers. Thus, no such prime exists, and $\gcd(a_j,b_j)=1$ for all $j$, as our choice of $j$ was arbitrary.

If the derived pairs are relatively prime, then $\gcd(a_j,b_j)=1$ for all pairs. Take any two distinct indices $s$ and $t$ that differ at bit position $j$. WLOG assume that $s$ has 1 and $t$ has 0. Therefore, $n_s \in A_j$ and $n_t \in B_j$. Suppose for the sake of contradiction that some prime $p|n_s$ and $p|n_t$. But we know that $n_s|a_j$ and $n_t|b_j$, so this implies that $p|a_j$ and $p|b_j$. But that contradicts the initial assumption about derived pairs being relatively prime. Therefore, the set of input numbers are pairwise relatively prime, since our choice of indices $s$ and $t$ was arbitrary.

3

Explaining the special case

For $k=4$ we see that $A_0=\{n_1,n_3\}$, $A_1=\{n_2,n_3\}$, $B_0=\{n_0,n_2\}$ and $B_1=\{n_0,n_1\}$. Therefore, the derived pairs are $(n_1n_3,n_0n_2)$ and $(n_2n_3, n_0n_1)$. They all satisfy the properties of being pairwise relatively prime. Notice that we are using 0-based indexing, so just shift indices by one to map them to those from the book.

Exercise 31.3-1

$$\def\arraystretch{1.5} \begin{array}{c:c:c:c:c} +_4 & 0 & 1 & 2 & 3 \\ \hdashline 0 & 0 & 1 & 2 & 3 \\ \hdashline 1 & 1 & 2 & 3 & 0 \\ \hdashline 2 & 2 & 3 & 0 & 1 \\ \hdashline 3 & 3 & 0 & 1 & 2 \end{array}$$

$$\def\arraystretch{1.5} \begin{array}{c:c:c:c:c} \cdot_5 & 1 & 2 & 3 & 4 \\ \hdashline 1 & 1 & 2 & 3 & 4 \\ \hdashline 2 & 2 & 4 & 1 & 3 \\ \hdashline 3 & 3 & 1 & 4 & 2 \\ \hdashline 4 & 4 & 3 & 2 & 1 \end{array}$$

There could be multiple one-to-one correspondeces showing that these groups are isomorphic. They share one common trait that neutral elements are always paired.

1. $f(0)=1,f(1)=3,f(2)=4,f(3)=2$

2. $f(0)=1,f(1)=2,f(2)=4,f(3)=3$

Exercise 31.3-2

Subgroups of $\Zeta_9$ are $\{0\}$, $\{0,3,6\}$ and $\Zeta_9$ itself. Subgroups of $\Zeta_{13}^*$ are $\{1\}$, $\{1,12\}$, $\{1,3,9\}$, $\{1,5,8,12\}$, $\{1,3,4,9,10,12\}$ and $\Zeta_{13}^*$ itself.

Exercise 31.3-3

Associativity is "inherited" from the group operation, as it doesn't depend on its arguments.

Since $S'$ is nonempty, there exists an element $a \in S'$. As $S' \subseteq S$ is finite, $a$ has a finite order $t=ord(a)$. By closure of $S'$, all powers of $a$ must lie in $S'$. Specifically, $a^t=e \in S'$. Similarly, an inverse of $a$ is $a^{t-1}$, since $a\cdot a^{t-1}=a^t=e$ and $a^{-1}=a^{t-1} \in S'$. We have not assumed anything special about $a$, hence our conclusion applies to all elements of $S'$. This finishes the proof.

Exercise 31.3-4

We simply apply equation (31.21) to get

$$\phi(p^e)=p^e\bigg(1-\frac{1}{p}\bigg)=p^e\bigg(\frac{p-1}{p}\bigg)=p^{e-1}(p-1)$$

Exercise 31.3-5

We proceed by showing the $f_a$ is a bijection. Any bijection from a set to itself is a permutation of that set. Since the domain and codomain of $f_a$ are of the same cardinality, it is enough to show that $f_a$ is a surjective function.

Select any $b \in \Zeta_n^*$. According to Theorem 31.13 the system $\Zeta_n^*$ is a finite abelian group. Consequently, $a^{-1} \in \Zeta_n^*$ and we have

$$f_a(a^{-1}b)=a(a^{-1}b)\!\!\!\!\mod n=(aa^{-1})b\!\!\!\!\mod n=b \!\!\!\!\mod n$$

Therefore, the preimage of $b$ under $f_a$ contains the element $a^{-1}b=ba^{-1} \text{ }(\!\!\!\!\mod n)$ (equality holds due to commutativity of $\Zeta_n^*$). This concludes the proof.

Exercise 31.4-1

We have $a=35$, $n=50$ and $b=10$. The extended version of Euclid's algorithm returns $(5,3,-2)$, so $d=5$ and $x_0=3(10/5)=6$. The step size is $50/5=10$, thus all solutions are $\{6,16,26,36,46\}$.

Exercise 31.4-2

Based on Corollary 31.26 there is a multiplicative inverse $a^{-1}\!\!\mod n$, so multiplying both sides of $ax=ay\space(\!\!\!\!\mod n)$ by $a^{-1}$ we get $a^{-1}ax=a^{-1}ay\space(\!\!\!\!\mod n)$, which implies that $x=y\space(\!\!\!\!\mod n)$. If $\gcd(a,n)>1$, then the previous conclusion is not valid. One counterexample is $2x=2y\space(\!\!\!\!\mod 4)$, where $x=1$ and $y=3$ is also a valid solution.

Exercise 31.4-3

Yes, it will work, forcing the procedure to emit solutions in sorted order. Among those $d$ distinct solutions, which are $n/d$ positions apart from each other, one will always belong to the interval $[0,n/d)$. Let it be $x_i=x'(b/d)+i(n/d)\space(\!\!\!\!\mod n)$ for some $i \in [0,d)$. Exercise 31.1.-7 implies that $x_i=x'(b/d)\space(\!\!\!\!\mod n/d)$, hence setting $x_0=x_i\space(\!\!\!\!\mod n/d)$ is the smallest starting value.

Exercise 31.4-4

This exercise is about the factor theorem applied modulo $p$. I recommend reading the proof based on Euclidean division of polynomials, which is aligned with the narrative from the book.

For deriving broader conclusions from the factor theorem, it is crucial for $p$ to be prime. For example, if $p=8$ then the polynomial $f(x)=x^2+7\space(\!\!\!\!\mod p)$ has 4 solutions $\{1,3,5,7\}$ modulo $p$ instead of $t=2$, where $t$ is a degree of $f$.

We proceed by induction on degree $t$. The base case $t=1$ follows from Corollary 31.25. For $t>1$ we have $f(x)=(x-a)g(x)$, so $f$ has at most $1+(t-1)=t$ distinct roots modulo $p$ (after applying the inductive hypothesis on $g(x)$). This concludes the proof for all $t \ge 1$.

Exercise 31.5-1

We follow the process outlined in Theorem 31.27. We have $x_1=4$, $n_1=5$, $x_2=5$ and $n_2=11$. We calculate $m_1=11$, $m_1^{-1}=1\space(\!\!\!\!\mod 5)$, $c_1=11\cdot 1=11$, $m_2=5$, $m_2^{-1}=9\space(\!\!\!\!\mod 11)$ and $c_2=5 \cdot 9=45$. Now we have all components to find $x=11\cdot4+45\cdot 5\space(\!\!\!\!\mod 55)$. Therefore, all solutions are of the form $49+55k$ for arbitrary integers $k$.

Exercise 31.5-2

We follow the steps outlined in Theorem 31.27. We have $m_1=56$, $m_1^{-1}=5\space(\!\!\!\!\mod 9)$, $c_1=280$, $m_2=63$, $m_2^{-1}=7\space(\!\!\!\!\mod 8)$, $c_2=441$, $m_3=72$, $m_3^{-1}=4\space(\!\!\!\!\mod 7)$ and $c_3=288$. We can now calculate $x=1 \cdot 280+2\cdot 441+3\cdot 288\space(\!\!\!\!\mod 504)$. Therefore, all solutions are of the form $10+504k$ for arbitrary integers $k$.

Exercise 31.5-3

Let $x=a^{-1}\space(\!\!\!\!\mod n)$. We simply employ equation (31.30) and Corollary 31.29 to get that $ax=1\space(\!\!\!\!\mod n)$ has a component-wise modular representation of $(1,1,\dots,1)$, where every component is $a_ix_i=1\space(\!\!\!\!\mod n_i)$. Therefore, $x_i=a_i^{-1}\space(\!\!\!\!\mod n_i)$. This concludes the proof.

Exercise 31.5-4

Let $n=\prod_{i=1}^k n_i$, where all terms of this product are pairwise relatively prime. According to Theorem 31.27 there is a one-to-one correspondence between a root of the equation $f(x)=0\space(\!\!\!\!\mod n)$ and its component-wise modular representation. Based on Corollary 31.29 we also have that $f(x)=0\space(\!\!\!\!\mod n)$ if and only if $f(x)=0\space(\!\!\!\!\mod n_i)$ for $i=1,2,\dots,k$. Furthermore, by the basic rules of modular arithmetic $f(x)=0\space(\!\!\!\!\mod n_i) \iff f(x \!\!\!\mod n_i)=0\space(\!\!\!\!\mod n_i)$.

Let a $k$-tuple $(a_1,a_2,\dots,a_k) \in \Zeta_{n_1} \times \Zeta_{n_2} \times \dots \times \Zeta_{n_k}$ be one solution of the system of equations $f(a_i)=0\space(\!\!\!\!\mod n_i)$ for $i=1,2,\dots,k$. Consequently, $a \in \Zeta_n$ computed from inputs $(a_1,a_2,\dots,a_k)$, by following the steps from Theorem 31.27, represents a zero of $f$ modulo $n$. Therefore, the number of such distinct $k$-tuples equals the number of roots of $f$ modulo $n$, and vice versa. This concludes the proof.

Exercise 31.6-1

Element	Order
1	1
2	10
3	5
4	5
5	5
6	10
7	10
8	10
9	5
10	2

The smallest primitive root is 2 and the indices $ind_{11,2}(x)$ of $x \in \Zeta_{11}^*$ are shown below.

Element	Index
1	0
2	1
3	8
4	2
5	4
6	9
7	7
8	3
9	6
10	5

Exercise 31.6-2

$$x^2=1\space(\!\!\!\!\!\!\mod p^e) \iff p^e|x^2-1 \iff p^e|(x-1)(x+1)$$

Exercise 31.6-3

Replace lines 6 and 7 with the following two lines:

else d = Modular-Exponentiation(a,(b-1)/2, n) // b is odd 
     return (a*d mod n)*d mod n

The return statement illustrates how to reduce the magnitude of intermediary results.

Exercise 31.6-4

Below is the iterative modular repeated squaring algorithm in Python 3.

def modular_exponentiation(a, b, n):
    result = 1
    d = a % n
    while b > 0:
        if b % 2 == 1:
            result = (result * d) % n
        d = (d * d) % n
        b >>= 1
    return result

Exercise 31.6-5

By Euler's theorem we know that $a^{\phi(n)}=1\space(\!\!\!\!\mod n) \iff aa^{\phi(n)-1}=1\space(\!\!\!\!\mod n)$. Therefore, we can calculate the inverse by calling $Modular\text{-}Exponentiation(a, \phi(n)-1,n)$.

Exercise 31.7-1

$\phi(n)=(p-1)(q-1)=280$, so $d=187\space(\!\!\!\!\mod 280)$. The encryption of the message $M=100$, by equation (31.37), is $P(100)=254$. You can test that everything is proper by calling $Modular\text{-}Exponentiation(254, 187,319)$ (see Exercise 31.6-4) and getting back the original message 100.

Exercise 31.7-2

Let$\beta$ denote the number of bits in $n$ and assume that $p$ and $q$ are large primes. As $e=3$, we have $3d=1\space(\!\!\!\!\mod \phi(n))$ that is equivalent to $3d-1=k(p-1)(q-1)$ for some integer $k$. Since $0<d<\phi(n)$ we know that $k=1 \lor k=2$. We can rewrite the previous expression as $3d-1=k(n-(p+q)+1)$. Apparently, $3d-1<n \implies k=1$ and $3d-1>n \implies k=2$.

We can find $x=p+q=n-(3d-1)/k+1$. Plugging in $q=n/p$ into the expression for $x$ we get $x=p+n/p \implies n=p(x-p)$. The last equation can be solved for $p$ using the quadratic formula. Obviously, once we have $p$ we can trivially find $q$.

All listed steps can be executed in time polynomial in $\beta$, hence the whole process is also doable in time polynomial in $\beta$.

Exercise 31.7-3

$$\begin{align*} P_A(M_1)P_A(M_2) &= M_1^eM_2^e\space(\!\!\!\!\!\!\mod n) \\ &= (M_1M_2)^e\space(\!\!\!\!\!\!\mod n) \\ &= P_A(M_1M_2) \end{align*}$$

Suppose an attacker possesses a ciphertext $C_A$ encrypted with $P_A$. She/he executes the following procedure:

1. Set $C=C_A$ and create an empty list $L$ containing temporary messages.

2. Try to decrypt $C$. Store the result in $M$.

3. If successful, then for each message $M_i$ in $L$, find its inverse $M_i^{-1}$ modulo $n$ and update $M=MM_i^{-1}\space(\!\!\!\!\mod n)$. At the end, $M=M_A$ and the process stops.

4. Otherwise, generate a new message $M_i \in \Zeta_n^*$, add it to $L$, and update $C=P_A(M_i)C$.

5. Goto step 2.

The chance of success at step 2 is 1%. The number of trials follows the geometric distribution with an expected value of 100. Finding inverses modulo $n$ is step 3 can be efficiently carried out using the extended Euclid's GCD algorithm. Almost all generated messages at step 4 will be relatively prime to $n$, since the chance of stumbling across one that contains a prime factor of $n$ is practically zero. All in all, an attacker can reveal the original message with high probability.

Exercise 31.8-1

One example is $n=7\cdot5=35$, where 6 is a nontrivial square root of 1 modulo 35, since $6^2=1\space(\!\!\!\!\mod 35)$. Such a root always exists for $n$ that satisfies the conditions from this exercise.

Decompose $n$ into a product $n_1n_2$, where $n_1$ and $n_2$ are odd numbers greater than 1 that are relatively prime to each other. By Corollary 31.28, there exists an $x$ simultaneously satisfying the equations

$$\begin{align*} x&=-1\space (\!\!\!\!\!\mod n_1) \\ x&=\space\space\space1\space (\!\!\!\!\!\mod n_2) \end{align*}$$

Corollary 31.29 gives that $x\neq±1\space (\!\!\!\!\mod n)$. On the other hand, we have

$$\begin{align*} x^2&=1\space (\!\!\!\!\!\mod n_1) \\ x^2&=1\space (\!\!\!\!\!\mod n_2) \end{align*}$$

Corollary 31.29 gives that $x^2=1\space (\!\!\!\!\mod n)$. Therefore, $x$ is a nontrivial square root of 1 modulo $n$.

Exercise 31.8-2

In number theory, $\lambda(n)$ is known as the Carmichael function.

Euler’s phi function is a multiplicative function that we can see after substituting $n=\prod_{i=1}^rp^{e_i}$ to get

$$\begin{align*} \phi(n)&=\phi(p_1^{e_1}\dots p_r^{e_r}) \\ &=p_1^{e_1}\dots p_r^{e_r}(1-1/p_1) \dots (1-1/p_r) && \text{(by equation (31.21))} \\ &=p_1^{e_1-1}(p_1-1)\dots p_r^{e_r-1}(p_r-1) \\ &=\phi(p_1^{e_1})\dots\phi(p_r^{e_r}) && \text{(by Exercise (31.3-4))} \\ \end{align*}$$

A least common multiple of two positive integers $a$ and $b$, represented with equations (31.11) and (31.12), respectively, can be calculated similarly to $\gcd(a,b)$ by replacing minimums with maximums in equation (31.13). This method, based on prime factorization, can be easily extended to arbitrary number of arguments (see also Exercise 31.2-8). In principle, $\text{lcm}(a_1,a_2,\dots,a_m)=a_1a_2\dots a_m/d$, where $d$ contains prime factors whose exponents compensate overshooting maximums, due to multiplication of numbers in the numerator, where powers simply add up. It follows that $\phi(n)$ is a multiple of $\lambda(n)$, thus $\lambda(n)|\phi(n)$. Another perspective is given here.

Suppose for the sake of contradiction that a Carmichael number $n$ is not "square-free", thus it has a factor $p_i^{e_i}$ where $e_i>1$. Consequently, $p_i|\phi(p_i^{e_i}) \implies p_i|\lambda(n)$, since $\lambda(n)$ is defined as a least common multiple of these individual Euler's phi functions. Furthermore, $p_i|n \implies p_i \nmid n-1$, which is a contradiction with the property that $\lambda(n)|n-1$ (see also Exercise 31.1-3). Therefore, $n$ must be "square-free."

Suppose for the sake of contradiction that a Carmichael number $n$ is consisted of two primes $p<q$. We have that $\lambda(n)=\text{lcm}(p-1,q-1) \implies q-1|\lambda(n)$. On the other hand, $q-1 \nmid n-1$ because by the Division theorem we have $n-1=pq-1=(q-1)p+(p-1)$. But this is again a contradiction with the property that $\lambda(n)|n-1$. Therefore, $n$ must be consisted of at least three primes.

Exercise 31.8-3

By Exercise 31.6-2 we have $x^2=1\space(\!\!\!\!\mod n) \iff n|(x-1)(x+1)$. If $x$ is a nontrivial square root of 1 modulo $n$, then by Corollary 31.35 $n$ is composite, so $2<x<n-1$. It follows that $n \nmid x-1$ and $n \nmid x+1$, thus prime factors of $n$ are distributed between these two terms of a product. Therefore, $\gcd(x-1,n)$ and $\gcd(x+1,n)$ are both nontrivial divisors of $n$.

Problem 31-1

a.

By Corollary 31.4, we have $\gcd(a,b)=\gcd(2(a/2),2(b/2))=2\gcd(a/2,b/2)$.

b.

By equation (31.13), $\gcd(a,b)$ doesn't have a prime factor 2. Dividing $b$ by 2 reduces the exponent of 2 in $b$, hence making it closer to zero. Consequently, $\gcd(a,b)=\gcd(a,b/2)$.

c.

Let $d_1=\gcd(a,b)$ and $d_2=\gcd(a-b,b)$. We proceed by showing that $d_1|d_2$ and $d_2|d_1$, thus according to equation (31.5) they are equal.

We know that $d_1|a$ and $d_1|b$, so by equation (31.4) we have $d_1|a-b$. Based on Corollary 31.3 we can conclude that $d_1|d_2$

We know that $d_2|a-b$ and $d_2|b$, so by equation (31.4) we have $d_2|(a-b)+b=a$. Based on Corollary 31.3 we can conclude that $d_2|d_1$.

Since $a-b$ is even and $b$ is odd, the division of $a-b$ by 2 is justified according to part (b).

d.

I recommend reading this study of the binary GCD algorithm with insightful C++ based optimizations.

Problem 31-2

In all subproblems below assume that $1<b \le a$, so that $q \ge 1$.

a.

We do all the arithmetic in binary by processing the bits of $a$ from the most significant to the least, accumulating the initial $O(\lg b)$ bits of $a$ into a value (current residue $r$) greater or equal than $b$, as they would anyhow produce leading zeros of a quotient.

In the analysis of the long division algorithm, the bits of the quotient and the divisor are counted differently because they play distinct roles. Each bit of $q$ is determined in one step of the algorithm. Thus, the number of steps required to compute all bits of $q$ is proportional to it's number of bits $\lfloor \lg q \rfloor+1=O(1+\lg q)$. This expression is nonzero even if $q \le1$.

The algorithm still requires at least one step to compare $a$ and $b$ even if $q=0$ (when $a<b)$. The expression $1+\lg q=1+0=1$ aims to encompass this case, despite $\lg q$ being undefined here.

At each step, the algorithm performs operations (e.g., comparisons or subtractions) involving the divisor $b$. Since it has approximately $O(\lg b)$ bits, these operations require that many bit operations per step. Therefore, the total count is $O(1+\lg q) \times O(\lg b)=O((1+\lg q)\lg b)$. This complexity reflects that the algorithm's time is dominated by the number of quotient bits (steps) and the size of the divisor (cost per step).

The remainder $r$ gets calculated along the way (see also Exercise 31.1-12).

b.

The reduction requires us to compute the remainder that can be accomplished in time as given in part (a). We know that $a=qb+r$, where $0 \le r < b$.

$$\begin{align*} \mu(a,b)-\mu(b,a \space \!\!\!\!\!\mod b) &= \mu(a,b)-\mu(b,r) \\ &=(1+\lg a)(1+\lg b)-(1+\lg b)(1+\lg r) \\ &=(1+\lg b)(\lg a-\lg r) \\ &> (1+\lg b)(\lg a-\lg b) \\ &=(1+\lg b)\lg(q+1) \end{align*}$$

Thus, we need to prove $c'(1+\lg q)\lg b < c'(1+\lg (q+1))\lg b \le c(1+\lg b)\lg (q+1)$.

$$\begin{align*} \frac{1+\lg (q+1)}{\lg (q+1)} &\le c''\frac{1+\lg b}{\lg b} && \text{(} c''=c/c' \text{)} \\ \frac{\lg b}{1+\lg b} \cdot \frac{1+\lg (q+1)}{\lg (q+1)} &\le 2 \le c'' \end{align*}$$

The last line follows from $\cfrac{x}{1+x} \le 1$ and $\cfrac{1+x}{x} \le 2$ for all $x \ge 1$. Therefore, for $c\ge2c'$ we have established the required proof.

c.

As shown in part (b), EUCLID takes at most $c(\mu(a,b)-\mu(b,a \space \!\!\!\!\mod b))$ bit operations on the first recursive call, at most $c(\mu(b,a \space \!\!\!\!\mod b)-\mu(a \space \!\!\!\!\mod b, b\space \!\!\!\mod (a \space \!\!\!\!\mod b)))$ on the second, and so on. This sum telescopes, hence we end up with $c\mu(a,b)-O(1)=O(\mu(a,b))$.

When applied to two $\beta$-bit inputs we get $O(\mu(a,b))=O((1+\beta)^2)=O(\beta^2)$.

Problem 31-3

a.

The algorithmic recurrence of the running time is $T(n)=T(n-1)+T(n-2)+\Theta(1)$. We use a substitution method to prove that this version cannot do better than being exponential in $n$. The constant $c_1$ denotes the lower bound in $\Theta(1)$.

Assume that $T(n) \ge cF_n$ for $n \ge 2$.

$$\begin{align*} T(n)&=T(n-1)+T(n-2)+\Theta(1) \\ &\ge cF_{n-1}+cF_{n-2}+c_1 && \text{(by the inductive hypothesis)} \\ &= cF_n+c_1 \\ &\ge cF_n \\ &\therefore T(n)=\Omega(F_n) \end{align*}$$

This concludes the proof, as Fibonacci numbers grow exponentially.

b.

Here is the Python 3 script showcasing memoization. The recurrence $T(n)=T(n-1)+\Theta(1)$ resolves to $T(n)=O(n)$, since memoization prevents repeated work.

import functools

@functools.cache
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(100))

It will print in the blink of an eye 354224848179261915075. Try commenting out the annotation to see the difference.

c.

We can leverage the repeated squaring method, with a small change, that instead of multiplying numbers we will work with small constant sized matrices. Each matrix operation will then also take constant time.

We prove the next statement using induction on $n$, following the hint from the book.

$$\begin{align*} \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^n &= \begin{bmatrix} F_{n-1} & F_n \\ F_n & F_{n+1} \end{bmatrix} \end{align*}$$

The base case $n=1$ obviously holds. For $n>1$ we have

$$\begin{align*} \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^n &= \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n-1} \\ &= \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} F_{n-2} & F_{n-1} \\ F_{n-1} & F_n \end{bmatrix} && \text{(by the inductive hypothesis)} \\ &= \begin{bmatrix} F_{n-1} & F_n \\ F_{n-2}+F_{n-1} & F_{n-1}+F_n \end{bmatrix} \\ &= \begin{bmatrix} F_{n-1} & F_n \\ F_n & F_{n+1} \end{bmatrix} \checkmark \end{align*}$$

At the end, we need to read out the matching cell containing $F_n$.

d.

Fibonacci numbers have $\beta=\Theta(n)$ binary digits, as explained here.

The bare recursive variant still has exponential running time. Increasing the amount of work at each level cannot invalidate the previously established lower bound.

The memoized version has a new recurrence $T(n)=T(n-1)+\Theta(n)$ that solves to $T(n)=\Theta(n^2)$.

The matrix version employs both addition and multiplication of numbers, hence it has a new recurrence $T(n)=T(n/2)+\Theta(n^2)$. Case 3 of the Master theorem states that $T(n)=\Theta(n^2)$.

Problem 31-4

a.

Theorem 31.32 implies that $\Zeta_p^*$ is a cyclic group, so it has a generator $g$, where all values $g^i$ modulo $p$ are distinct for $i=0,1,\dots,p-2$. Every even index is associated with a quadratic residue, since ${(g^{i/2}})^2=g^i\space(\!\!\!\!\mod p)$. Thus, the number of quadratic residues is at least $(p-1)/2$.

Suppose for the sake of contradiction that there is also some odd index $i$ such that $x^2=g^i\space(\!\!\!\!\mod p)$ for some $x$. We must have that $x=g^j\space(\!\!\!\!\mod p)$ and $g^{2j}=g^i\space(\!\!\!\!\mod p)$. Theorem 31.33 implies that $2j=i\space(\!\!\!\!\mod \phi(p))$, where $\phi(p)=p-1$. But this is impossible, since $p-1 \nmid 2j-i$ due to mismatch in parity. We can conclude that the the number of quadratic residues is exactly $(p-1)/2$.

b.

If $a$ is a quadratic residue modulo $p$, then there is an $x$ such that

$$a^{(p-1)/2}=(x^2)^{(pi-1)/2}=x^{p-1}=1=\bigg(\frac{a}{p}\bigg)\space(\!\!\!\!\!\mod p) \space\space\space\space\text{ (by Fermat's theorem)}$$

Otherwise, $g^i=a\space(\!\!\!\!\mod p)$ for some odd index $i$ (see part(a)). Let $x=g^{(p-1)/2}$. Theorem 31.34 implies that $x^2=1\space(\!\!\!\!\mod p)$ has only two possible solutions $x=1 \lor x=-1$. According to Fermat's theorem $g^{p-1}=g^0=1\space(\!\!\!\!\mod p)$, so it must be that $g^{(p-1)/2}=-1\space(\!\!\!\!\mod p)$, as powers of $g$ are distinct for $i=0,1,\dots,p-2$. We have

$$a^{(p-1)/2}=(g^i)^{(p-1)/2}=(g^{(p-1)/2})^i=(-1)^i=-1=\bigg(\frac{a}{p}\bigg)\space(\!\!\!\!\!\mod p)$$

We can call modular_exponentiation(a, (p-1)/2, p) (see Exercise 31.6-4) and check whether the returned value is 1. If we let $\beta=\lg p$, then It requires $O(\beta^3)$ bit operations.

c.

By part (b), $a^{(p-1)/2}=a^{2k+1}=1\space(\!\!\!\!\mod p)$, so $(a^{k+1})^2=a^{2k+2}=a\cdot a^{2k+1}=a\space(\!\!\!\!\mod p)$. Therefore, $a^{k+1}$ is a square root of $a$ modulo $p$. We can again use modular exponentiation to efficiently find it using $O(\beta^3)$ bit operations.

d.

Run the algorithm of part (b) by repeatedly trying random numbers $a \in [2,p)$ until $\big(\frac{a}{p}\big)=-1\space(\!\!\!\!\mod p)$. Half the elements in $\Zeta_p^*$ are not quadratic residues, thus each experiment can be regarded as a Bernoulli trial with probability 1/2. The expected number of trials follows the geometric distribution and equals 2. The average number of arithmetic operations is $O(\beta)$.