This theorem is obviously correct. Now I try to prove it by well-ordering principle.
But I don't know where to start the proving....
$\endgroup$2 Answers
$\begingroup$Theorem: For every pair of integers $a,b$ where $b≠0$, there exists unique integers $q,r$ such that $a=qb+r$ and $0≤r<|b|$.
Existence
Consider the following progression: $$…,a−3b,a−2b,a−b,a,a+b,a+2b,a+3b,…$$ This extends in both directions. By the Well-Ordering Principle, there must exist a smallest non-negative element, $x$. Thus, $x=a−qb$ for some $q∈\mathbb{Z}$. $x$ must be in the interval $[0,b)$ because otherwise $r−b$ would be smaller than $r$ and a non-negative element in the progression.
Uniqueness
Suppose we have another pair $q_0$ and $r_0$ such that $a=bq_0+r_0$, with $0≤r_0<b$. $$ bq+r=bq_0+r_0.$$ We see that $r−r_0=b(q_0−q)$, and so $b\setminus (r−r_0)$. Since $0≤r<b$ and $0≤r_0<b$, we have that $−b<r−r_0<b.$ Hence, $r−r_0=0\implies r=r_0$. So $r−r_0=0=b(q_0−q)$ which implies that $q=q_0$. This shows uniqueness.
For an alternative proof, see .
$\endgroup$ 4 $\begingroup$Suppose $\,S\subset \Bbb Z \,$ and $\,0<b\in\Bbb Z.\,$ If $\,S\,$ has a nonnegative integer $\,a,\,$ and $\,n\in S\,\Rightarrow\,n\!-\!b\in S\,$ then $\,S\,$ has least nonnegative element $\,\ell < b\,$ (otherwise $\,\ell\!-\!b\in S\,$ and $\,0 < \ell\! -\!b < \ell,\,$ contra minimality of $\,\ell).\,$ Therefore if $\ a\ge 0\,$ then $\,S = a-b\,\Bbb Z\,$ has least nonnegative element $< b.$
$\endgroup$
