1
$\begingroup$

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.

  • 1
    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$.2012-01-30

2 Answers 2

2

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$.

  • 0
    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$.2012-01-30
0

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$