Define a function fm: N x N ->N as follows: fm(n, k) =k if 0 ≤ n < m, and fm(n, k) =fm(n-m, k+1) otherwise. Describe in terms of a single well-known arithmetic operation what fm(n, 0) is computing.

If 0 ≤ n < m, then fm(n,0) = 0

Suppose m ≤ n < 2m

fm(n, 0) = fm(n-m, 0+1)

Now m – m ≤ n - m < 2m – m

=> 0 ≤ n – m < m

=> fm(n – m, 0 + 1) – 0 + 1 = 1

=> fm(n, 0) = 1 for m ≤ n < 2m

Suppose 2m ≤ n < 3m

fm(n,0) = fm(n – m, 0 + 1)

Now 2m – m ≤ n – m < 3m – m

=> m ≤ n – m < 2m

=> fm(n – 2m, 2) = 2

=> fm(n – m, 0 + 1) = 2

=> fm(n, 0) = 2 for 2m ≤ n < 3m

And so on

In other words, fm(n, 0) is computing the quotient of n ÷ m