[proofplan]
We construct the remainder by looking among all nonnegative integers congruent to $a$ modulo $n$ and choosing the least one by the [well-ordering principle](/theorems/721). The minimality forces the chosen remainder to be strictly smaller than $n$, because otherwise subtracting $n$ would produce a smaller admissible nonnegative integer. Uniqueness follows by subtracting two decompositions and observing that the difference of two possible remainders is a multiple of $n$ whose absolute value is smaller than $n$. The residue-class formulation is then exactly the same uniqueness statement expressed in quotient notation.
[/proofplan]
[step:Choose the least nonnegative integer congruent to $a$ modulo $n$]
Fix $a \in \mathbb{Z}$. Define the subset $S \subset \mathbb{Z}$ by
\begin{align*}
S = \{a-kn \in \mathbb{Z} : k \in \mathbb{Z},\ a-kn \ge 0\}.
\end{align*}
The set $S$ is nonempty. Indeed, let $m=|a| \in \mathbb{Z}$ and choose $k=-m$. Then
\begin{align*}
a-kn = a+mn.
\end{align*}
If $a \ge 0$, then $a+mn \ge 0$. If $a<0$, then $m=-a$, so
\begin{align*}
a+mn = -m+mn = m(n-1) \ge 0,
\end{align*}
because $n \ge 1$. Thus $S$ contains at least one nonnegative integer.
By the well-ordering principle, the nonempty set $S$ of nonnegative integers has a least element. Let $r \in S$ denote this least element. Since $r \in S$, there exists an integer $q \in \mathbb{Z}$ such that
\begin{align*}
r = a-qn.
\end{align*}
Rearranging gives
\begin{align*}
a = qn+r.
\end{align*}
[guided]
Fix $a \in \mathbb{Z}$. We want to find a remainder $r$ satisfying two conditions: first, $r$ should differ from $a$ by a multiple of $n$, and second, it should be nonnegative. The natural set to examine is therefore
\begin{align*}
S = \{a-kn \in \mathbb{Z} : k \in \mathbb{Z},\ a-kn \ge 0\}.
\end{align*}
This set consists exactly of the nonnegative integers obtained from $a$ by subtracting an integer multiple of $n$.
Before applying the well-ordering principle, we must verify that $S$ is nonempty. Let $m=|a| \in \mathbb{Z}$ and choose the integer $k=-m$. Then the corresponding element has the form
\begin{align*}
a-kn = a+mn.
\end{align*}
If $a \ge 0$, then $a+mn \ge 0$ because both $a$ and $mn$ are nonnegative. If $a<0$, then $m=-a$, and hence
\begin{align*}
a+mn = -m+mn = m(n-1).
\end{align*}
Since $n>0$ and $n \in \mathbb{Z}$, we have $n \ge 1$, so $m(n-1)\ge 0$. Thus in all cases $S$ contains at least one nonnegative integer.
Now the well-ordering principle applies to $S$, since $S$ is a nonempty set of nonnegative integers. Let $r$ be the least element of $S$. By the definition of $S$, there is an integer $q \in \mathbb{Z}$ such that
\begin{align*}
r = a-qn.
\end{align*}
Solving this equation for $a$ gives
\begin{align*}
a = qn+r.
\end{align*}
Thus we have produced integers $q$ and $r$ with the desired algebraic form, and the remaining task is to prove that this least nonnegative choice actually satisfies $r<n$.
[/guided]
[/step]
[step:Use minimality to prove the remainder is smaller than $n$]
We already know $r \ge 0$ because $r \in S$. Suppose, for contradiction, that $r \ge n$. Since $r=a-qn$, define
\begin{align*}
r' = r-n.
\end{align*}
Then $r' \ge 0$, and
\begin{align*}
r' = a-qn-n = a-(q+1)n.
\end{align*}
Hence $r' \in S$. But $r'=r-n<r$ because $n>0$, contradicting the minimality of $r$ in $S$. Therefore $r<n$. We have shown that there exist $q,r \in \mathbb{Z}$ such that $a=qn+r$ and $0 \le r<n$.
[/step]
[step:Subtract two decompositions to prove uniqueness]
Suppose that $q,r,q',r' \in \mathbb{Z}$ satisfy
\begin{align*}
a = qn+r
\end{align*}
and
\begin{align*}
a = q'n+r',
\end{align*}
with $0 \le r<n$ and $0 \le r'<n$. Subtracting the two equalities gives
\begin{align*}
(q-q')n = r'-r.
\end{align*}
Thus $r'-r$ is an integer multiple of $n$.
The inequalities on $r$ and $r'$ give
\begin{align*}
-(n-1) \le r'-r \le n-1.
\end{align*}
Hence
\begin{align*}
|r'-r| < n.
\end{align*}
If $r'-r=tn$ for some $t \in \mathbb{Z}$ and $t \ne 0$, then $|r'-r|=|t|n \ge n$, contradicting $|r'-r|<n$. Therefore $t=0$, so
\begin{align*}
r'=r.
\end{align*}
Substituting this into $(q-q')n=r'-r$ gives
\begin{align*}
(q-q')n=0.
\end{align*}
Since $n>0$, we have $n \ne 0$, and hence $q=q'$. This proves uniqueness of both $q$ and $r$.
[/step]
[step:Translate the division statement into canonical residue representatives]
Let $\bar{a}$ be a residue class in $\mathbb{Z}/n\mathbb{Z}$, represented by some $a \in \mathbb{Z}$. By the existence part, there are $q,r \in \mathbb{Z}$ such that
\begin{align*}
a = qn+r
\end{align*}
and $0 \le r<n$. Therefore
\begin{align*}
a-r = qn,
\end{align*}
so $a \equiv r \pmod{n}$. Hence $\bar{a}=\bar{r}$, and the class $\bar{a}$ contains a representative $r \in \{0,1,\ldots,n-1\}$.
For uniqueness, suppose $r,r' \in \{0,1,\ldots,n-1\}$ and $\bar{r}=\bar{r'}$ in $\mathbb{Z}/n\mathbb{Z}$. Then $r \equiv r' \pmod{n}$, so $r-r'$ is a multiple of $n$. Since both $r$ and $r'$ lie between $0$ and $n-1$, we have $|r-r'|<n$. An integer multiple of $n$ with absolute value strictly less than $n$ must be $0$, so $r-r'=0$. Thus $r=r'$. Therefore every residue class modulo $n$ has a unique representative in $\{0,1,\ldots,n-1\}$.
[/step]
