[proofplan] Fix $k \in \mathbb{N}$ and prove the assertion for all $n \in \mathbb{N}$ by [induction](/pages/mathematical-induction) on $n$. The base case $n = 1$ splits according to whether $k = 1$ or $k \ge 2$. In the inductive step, an expression $n = qk + r$ is converted into one for $n + 1$ by either increasing the remainder or, when the remainder has reached $k - 1$, resetting the remainder to $0$ and increasing the quotient. [/proofplan] [step:Fix the divisor and formulate the induction statement] Let $k \in \mathbb{N}$ be fixed. For each $n \in \mathbb{N}$, let $P(n)$ denote the statement that there exist integers $q$ and $r$ such that \begin{align*} n = qk + r \end{align*} and \begin{align*} 0 \le r \le k - 1. \end{align*} It suffices to prove $P(n)$ for every $n \in \mathbb{N}$, because $k \in \mathbb{N}$ was arbitrary. [/step] [step:Verify the base case $n = 1$] If $k = 1$, take $q := 1$ and $r := 0$. Then $q,r \in \mathbb{Z}$ and \begin{align*} 1 = 1 \cdot 1 + 0 = qk + r. \end{align*} Also $k - 1 = 0$, so \begin{align*} 0 \le r = 0 \le k - 1. \end{align*} If $k \ge 2$, take $q := 0$ and $r := 1$. Then $q,r \in \mathbb{Z}$ and \begin{align*} 1 = 0 \cdot k + 1 = qk + r. \end{align*} Since $k \ge 2$, we have $1 \le k - 1$, hence \begin{align*} 0 \le r = 1 \le k - 1. \end{align*} Thus $P(1)$ holds. [/step] [step:Convert a representation of $n$ into a representation of $n + 1$] Assume $n \in \mathbb{N}$ and assume the induction hypothesis $P(n)$. Then there exist integers $q$ and $r$ such that \begin{align*} n = qk + r \end{align*} and \begin{align*} 0 \le r \le k - 1. \end{align*} If $r < k - 1$, define $q_1 := q$ and $r_1 := r + 1$. Then $q_1,r_1 \in \mathbb{Z}$, and \begin{align*} n + 1 = qk + r + 1 = q_1 k + r_1. \end{align*} Because $r \ge 0$, we have $r_1 = r + 1 \ge 1 \ge 0$. Because $r < k - 1$ and $r,k \in \mathbb{Z}$, we have $r + 1 \le k - 1$. Hence \begin{align*} 0 \le r_1 \le k - 1. \end{align*} If $r = k - 1$, define $q_1 := q + 1$ and $r_1 := 0$. Then $q_1,r_1 \in \mathbb{Z}$, and \begin{align*} n + 1 &= qk + r + 1 \\ &= qk + (k - 1) + 1 \\ &= qk + k \\ &= (q + 1)k + 0 \\ &= q_1 k + r_1. \end{align*} Since $k \in \mathbb{N}$, we have $k \ge 1$, so \begin{align*} 0 \le r_1 = 0 \le k - 1. \end{align*} Therefore $P(n+1)$ holds. [guided] Assume $n \in \mathbb{N}$ and assume the induction hypothesis $P(n)$. This means that there are integers $q$ and $r$ with \begin{align*} n = qk + r \end{align*} and \begin{align*} 0 \le r \le k - 1. \end{align*} We must produce integers giving the same kind of expression for $n+1$. There are two possible positions for the current remainder $r$. First suppose $r < k - 1$. Since $r$ and $k$ are integers, this strict inequality implies \begin{align*} r + 1 \le k - 1. \end{align*} Define $q_1 := q$ and $r_1 := r + 1$. These are integers, and adding $1$ to the induction-hypothesis identity gives \begin{align*} n + 1 = qk + r + 1 = q_1 k + r_1. \end{align*} The lower bound follows from $r \ge 0$: \begin{align*} r_1 = r + 1 \ge 1 \ge 0. \end{align*} Together with $r_1 \le k - 1$, this gives \begin{align*} 0 \le r_1 \le k - 1. \end{align*} Now suppose $r = k - 1$. In this case increasing the remainder by $1$ would give $k$, which is outside the required range. Instead define $q_1 := q + 1$ and $r_1 := 0$. These are integers, and substituting $r = k - 1$ gives \begin{align*} n + 1 &= qk + r + 1 \\ &= qk + (k - 1) + 1 \\ &= qk + k \\ &= (q + 1)k + 0 \\ &= q_1 k + r_1. \end{align*} Because $k \in \mathbb{N}$ and natural numbers start at $1$, we have $k \ge 1$, so $k - 1 \ge 0$. Therefore \begin{align*} 0 \le r_1 = 0 \le k - 1. \end{align*} Thus in both cases we have found integers $q_1$ and $r_1$ satisfying the required identity and remainder bound for $n+1$. [/guided] [/step] [step:Apply induction and restore the arbitrary divisor] The base case proves $P(1)$, and the inductive step proves that $P(n)$ implies $P(n+1)$ for every $n \in \mathbb{N}$. By the Principle of Mathematical Induction, $P(n)$ holds for every $n \in \mathbb{N}$. Since the fixed divisor $k \in \mathbb{N}$ was arbitrary, for every $n,k \in \mathbb{N}$ there exist integers $q$ and $r$ such that \begin{align*} n = qk + r \end{align*} and \begin{align*} 0 \le r \le k - 1. \end{align*} This is the desired conclusion. [/step]