# Proof of existence quotient and remainder in $\mathbb Z$

Suppose $a = qb + r$, for $a,q,b,r \in \mathbb{Z}$ and $0 \le |r|<|b|$, $|b| > 0$, then $q$ is called the quotient and $r$ the remainder. Is the following proof of the existence of $q$ and $r$ valid?

Let $P(a,b)\$ be the statement that there exists a quotient and a remainder for this $a$ and $b$. Now first I will prove $P(0,b)$: take $q=0, r=a$.

Now I will prove $P(a+1,b)$. Suppose $P(a,b)$. Then there are integers $q$ and $r$ satisfying $a=qb+r$. So $a+1=qb+(r+1)$. There are two cases: $(1)\$ $|r+1|<|b|$, and $(2)\$ $|r+1|\ge|b|$.

$(1)\$ If $|r+1|<|b|$ then we are done: since $0 \le |r+1| < |b|$, we found a quotient $q$ and a remainder $r+1$.

$(2)\$ Now the other part: $|r+1|\ge|b|$. Since $|r|<|b|$, we have $|r+1|=|b|$, which implies $$a=qb+r \Rightarrow a+1=qb+(r+1) \Rightarrow a+1=qb \pm b \Rightarrow a+1 = (q \pm 1) b.$$ So we found quotient a $q \pm 1$ and a remainder $0$. So $P(a+1,b)$ holds. We can prove $P(a-1,b)$ in a similar way. And thus, for all $a \in \mathbb{Z}$, the statement $P(a,b)$ holds.

-
Your proof only establishes the result for $a\geq 0$. You still need to do the case of $a\lt 0$. As a minor aside, somewhere along the line you need to say that $b\neq 0$. – Arturo Magidin Jan 30 '12 at 16:20

This is a valid proof. Its only disadvantage is that you cannot easily generalise this proof for rings other than $\mathbb{Z}$ e.g. the polynomial ring $K[X]$ over a field $K$.

-
Thanks, later in the book they proof it for polynomials, but they use some other proof which is at this point not very logical and clear to me, but maybe they do that so it's easier to understand it for polynomials. – Kevin Jan 30 '12 at 11:44
I'm not sure the proof is complete. The argument shows that it holds for $a=0$, and that if it holds for $a$ then it holds for $a+1$. This does not suffice to show it holds for, say, $a=-1$. – Arturo Magidin Jan 30 '12 at 16:40

I don't really understand your arguments. Here is what I believe is a standard proof.

Let $a$ and $b$ be integers. Assume $b\neq0$. Then there is a unique pair $(q,r)$ of integers satisfying $$a=bq+r,\quad0\le r < |b|.$$ Proof of uniqueness. Let us put $$R':=\{a-bx\ |\ x\in\mathbb Z \},\quad R:=R\cap\mathbb N.$$ It suffices to check $r=\min R$. Assume by contradiction that there is an $s$ in $R$ satisfying $s < r$. As $$0 < r-s=(a-bx)-(a-by)=b\ (y-x),$$ we have $|b|\le r-s\le r$, contradiction.

Proof of existence. We have $$a-b\ (-|a|\,b)=a+|a|\ b^2\in R\neq\varnothing.$$ It suffices to show $$r:=\min R < |b|.$$ The inequality $r\ge|b|$ would imply $r-|b|\in R$, contradicting the minimality of $r$

-