Let $n \in \mathbb{N}$. For every $m \in \mathbb{Z}$, there exist unique $q, r \in \mathbb{Z}$ such that $ m = qn+r$ and $0 \le r \le n-1$. We call $q$ the quotient and $r$ the remainder when dividing into $m$.
I'm having trouble proving this with induction. I believe the idea is to first prove for all $m \in \mathbb{Z} _{\ge 0}$ by induction, then prove for all $m \in \mathbb{Z}$ but $m \notin \mathbb{Z} _{\ge 0}$ using the induction proof on $-m$, since $-m \in \mathbb{N}$.
I'd appreciate any help, thank you.
$\endgroup$6 Answers
$\begingroup$Uniqueness doesn't need induction. Suppose $m=qn+r=q'n+r'$, where $0\le r\le n-1$. It's not restrictive to assume $r\le r'$, so we have $0\le r'-r\le n-1$; but $r'-r=n(q-q')$, so $$ 0\le n(q-q')<n $$ As $n>0$, this implies $$ 0\le q-q'<1 $$ so $q=q'$ and therefore $r'=r$.
The proof of existence can be conveniently split into the cases $m\ge0$ and $m<0$.
The first case is done by induction. The case $m=0$ is obvious: take $q=0$ and $r=0$. Assume you know $m=qn+r$, with $0\le r<n$; then $$ m+1=qn+r+1 $$ If $r+1=n$, then $m+1=q(n+1)+0$, otherwise $r+1<n$ (using the hypothesis that $r\le n-1$, so $r+1\le n$) and the assert is true.
Now let's prove the case $m<0$. From the first case we get $$ -m=qn+r $$ with $0\le r<n$. If $r=0$, then $m=(-q)n+0$ and we're done. Otherwise $0<r<n$ and $$ m=(-q)n-r=(-q)n-n+n-r=(-q-1)n+(n-r) $$ where $0<n-r<n$ and we're done.
$\endgroup$ 4 $\begingroup$Base case, $m=0$:$$0=0n+0, 0\le0<n.$$
For any other $q$, we have $qn\le-n\lor qn\ge n$, and as $r=-qn$, $r\ge n\lor r\le-n$, which is not allowed.
Induction, $m\to m+1$:
$$m=qn+r\iff m+1=qn+r+1$$
if $0\le r+1<n$, all conditions are met;
if $r+1=n$, take $q'=q+1,r'=0$ and $$m+1=q'n+r',0\le r'<n.$$
Theorem : If $a,b∈ ℤ$ such that $ b>0$ then$\exists!$ $q,r\in$ Z such that $a=bq+r$ , $0≤r<b$
Proof : Consider, $S=\big\{ a-nb≥0 | n\in Z \big\}$
First thing to prove that $S≠∅$
It is clear that $a-(-|a|)b ≥ 0 $
So $a-(-|a|)b\in S$
Hence $S≠∅$
By WOP , there exists $r=min(S)$
So, $r = a-qb$ for $q\in\mathbb{Z}$
Hence, $a = bq+r$
So Here Existence part completes here!!
Now we have to prove that $r<b$
Let's assume to the contrary that $r≥b$
So, $r-b≥0$
since $r=a-qb$
So $a-qb-b≥0$
$a-(q+1)b≥0$
So, $r-b\in$ S
Since $r-b<r$ ( because $b>0$ )
This contradicts the minimality of $r$
Hence $r < b$
This completes our proof !!!
I am sorry that I couldn't provide the uniqueness part of division algorithm
Hope it helps 😋😋
$\endgroup$ 0 $\begingroup$Well lets take $m=1$ $$1=qn+r\\$$ If $qn$ is negative $r$ would have to be greater than $n-1$ so that is out,if $qn$ is positive $q=1$ and $r=1-n$ and since $r\geq 0$,if $qn=0$,$r=1$ so it's unique now lets take $$m=an+l\\m+1=an+l+1$$ If $l+1=n$ then $m+1=(a+1)n+0$ which is unique since a is fixed(unique),otherwise since both $a$ and $l$ are fixed so are $an$ and $l+1$
$\endgroup$ $\begingroup$(I). Let $P(s)$ denote a statement about s, which may or may not be true. The Principle of Induction :
If (i) $P(1)$ is true,
and if (ii) For all $s\in \mathbb N\;(P(s)\implies P(s+1),$
then (iii) $P(s)$ is true for all $s\in \mathbb N.$
Digression: If (ii) is true, it does not follow that $P(s)$ is true for any $s.$ For example if $P(s)$ is "$s<s$" then (ii) is true ( although (i) is false).
Equivalent to the Principle of Induction is the Well-Ordering Principle:
If $P(s)$ is true for some $s\in \mathbb N$ then there is a least $s\in \mathbb N$ for which $P(s)$ is true.
(II). By Induction we get the Archimedean property of $\mathbb N:$ For any $x,y \in \mathbb N$ there exists $z\in \mathbb N$ such that $x< zy.$
Proof: Let $P(s)$ be " There exists $z$ with $s< yz"$. (So $P(s)$ is "$s$ is less than some multiple of $y$".) We have:
(i). $P(1)$ because $1<2y.$
(ii). $(P(s)\implies P(s+1))$ for each $s,$ because if $s< yz$ then $$s+1< yz+1< yz+2y=y(z+2).$$ So by Induction, $P(s)$ holds for all $s.$ In particular $P(x)$ is true.
(III). So for $n,m\in \mathbb N,$ there exists $z\in \mathbb N$ such that $m< zn.$ By the Well-Ordering Principle, let $q'$ be the least such $n.$ We have $(q'-1)n\leq m<q'n.$ (This is immediate if $q'=1.$ If $q'>1$ then $q'>q-1\in \mathbb N,$ and then the def'n of $q'$ implies $(q'-1)n\leq m.$)
Let $q=q'-1.$ So $qn\leq m<(q+1)n.$ Let $r=m-qn.$ Then $$0=qn-qn\leq m-qn=r<(q+1)n-qn=n.$$ And of course $m=qn+r.$
Now if $m=q_1n+r_1$ with for integers $q_1,r_1$ with $0\leq r_1<n$ then $$0=m-m=(qn+r)-(q_1n+r_1)=(q-q_1)n+(r-r_1),$$ so $|r-r_1|=|(q-q_1)n|.$ This is impossible if $q_1\ne q.$ Because (i). $q_1\ne q\implies |(q-q_1)n|\geq n,$ but (ii). $|r-r_1|<n$ because $$(0\leq r<n \land 0\leq r_1<n)\implies (\;(r-r_1<n-0=n) \land (r_1-r<n-0=n)\;).$$
Since $q_1=q$ we have $r_1=q_1n -m=qn-m=r.$
I will leave the case $m\leq 0$ to you.
$\endgroup$ $\begingroup$Recall the definition/notation of an interval of integers: for integers $k$ and $j$ with $k \le j$,
$$[k,j] = \{m \in \Bbb Z \text{ | } k \le m \le j\}$$
Let $b \in \Bbb Z$ be a given integer satisfying $b \ge 1$ and set
$$\tag 1 \mathcal R = [0,b-1]$$
Define the function
$$ \tag 2 \Omega: \Bbb Z \times \mathcal R \to \Bbb Z \\ \quad \quad \quad \;(q,r) \; \; \mapsto bq + r $$
For each $n \ge 0$, set$$\tag 3 A_n =[-n,n] \times \mathcal R$$
and denote the restriction of $\Omega$ to $A_n$ by $\Omega_n$.
Theorem 1: The mapping $\Omega$ is a bijection.
Proof
We claim that for every $n \ge 0$ the mapping $\Omega_n$ is injective with
$$\tag 4 \Omega_n(A_n) = [-bn, bn + b-1]$$
The proof will use induction on $n$.
For $n = 0$, $\Omega_0(q_0,r_0) = \Omega_0(q_1,r_1)$ means $q_0 = q_1 = 0$ and $r_1 = r_0$, so $\Omega_0$ is an injection. The image of $\Omega_0$ is equal to $\mathcal R$ but that can also be expressed by setting $n = 0$ in the rhs of $\text{(4)}$.
Assume that for $n \ge 0$ the mapping $\Omega_n$ is injective with image given by $\text{(4)}$.
To show that $\Omega_{n+1}$ is an injection assume that
$$\tag 5 \Omega_{n+1} (q_0,r_0) = \Omega_{n+1}(q_1,r_1)$$
Now if both $(q_0,r_0)$ and $(q_1,r_1)$ belonged to the domain of $\Omega_n$, injectivity would follow from the inductive hypothesis. So need only check when $q_0 \in \{-(n+1),n+1\}$ or $q_1 \in \{-(n+1),n+1\}$. Before continuing, observe that for any $r \in \mathcal R$,
$$\tag 6 b(-(n+1)) + r \lt -bn \lt bn + b - 1 \lt b(n+1) + r$$
But then $\text{(5)}$, $\text{(6)}$ and the inductive hypotheses together imply that there are only two cases that have to be checked,
$\quad q_0 = q_1 = -(n+1)$
and
$\quad q_0 = q_1 = n$
In either case we conclude that $r_0 = r_1$ and injectivity is established.
An easy argument from here shows that
$$\tag 7 \Omega_{n+1}(A_{n+1}) \subset [-b(n+1),\, b(n+1) + b-1]$$
The number of elements in the interval on the rhs of $\text{(7)}$ is given by
$$\tag 8 b(n+1) + b-1-[-b(n+1)] + 1$$
and simplifying we get a count of $b(1+2(n+1))$, which is also the number of elements in $A_{n+1}$. Using an alternate formulation of the the pigeonhole principle, $\Omega_{n+1}$ is a surjection satisfying $\text{(4)}$.
The induction has been completed.
To complete the proof we will show that $\Omega$ is both injective and surjective.
Suppose $\Omega (q_0,r_0) = \Omega(q_1,r_1)$. Setting $n = \text{max}(|-q_0,q_0,-q_1,q_1)$, we have $(q_0,r_0), (q_1,r_1) \in A_n$ and so $\Omega$ is injective.
Any integer $m \in \Bbb Z$ belongs to some interval of the form given by $\text{(4)}$ which is the range of $\Omega_n$.
So $\Omega$ is also a surjection. $\quad \blacksquare$
