Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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$. –  Arturo Magidin Jan 30 '12 at 16:20

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.