MATH.4:5.1 - Obtain quotient and remainder together
Given a natural number n and a fixed positive integer d, construct natural numbers q,r such that n=q*d+r and 0≤r<d.
At n=0, return (0,0). The equation holds, and positivity of d gives the remainder bound.
Suppose the result for n is (q,r). To obtain the result for n+1:
- if
r+1<d, return(q,r+1); - otherwise return
(q+1,0).
Because r<d and the values are integers, the second branch has r+1=d. In the first branch, n+1=q*d+(r+1); in the second, n+1=(q+1)*d+0. Both branches preserve the required bound. This proves the recursive construction for all natural-number inputs.
For d=3, successive witnesses include:
Input n | Witness (q,r) |
|---|---|
| 0 | (0,0) |
| 1 | (0,1) |
| 2 | (0,2) |
| 3 | (1,0) |
| 4 | (1,1) |
| 5 | (1,2) |
| 6 | (2,0) |
| 7 | (2,1) |
| 8 | (2,2) |
The output for 8 determines both two completed groups of three and a remainder of two. Keeping only the remainder would lose the number of completed groups. MATH.2 explains which questions such a reduced result can still answer.
The construction takes one successor step per unit of n. It exposes the witness and proof economically as mathematics, but a large encoded integer can call for a different division algorithm. If division with the same convention is already supplied, use that operation.
Changing the parameter to d=0 defeats the specification: no natural r satisfies 0≤r<0. This returns a failed input condition before any recursive step. Extending the input to negative integers also requires a new case; the natural-number recursion does not cover that extension.