Generalize the parity(n) algorithm to remainder(n, k) to recursively compute the number r ∈ {0, 1, . . . , k − 1} such that remainder(n, k) = n mod k. Assume that k ≥ 1 and n ≥ 0 are both integers,...

Generalize the parity(n) algorithm to remainder(n, k) to recursively compute the number r ∈ {0, 1, . . . , k − 1} such that remainder(n, k) = n mod k. Assume that k ≥ 1 and n ≥ 0 are both integers, and follow the same algorithmic outline as in Figure 5.25. Prove your algorithm correct using strong induction on n.

Figure 5.25: A reminder of the parity algorithm (from Figure 5.16), and an algorithm to convert an integer to binary