Prove by induction $n= qb+r$ for $ n\ge 0$

593 Views Asked by At

This is a problem given in Tom Apostol's Calculus Vol. 1 Let $b$ be a fixed positive integer. Prove the following by induction for all $ n\ge 0$: There exists $q$ and $r$ $\{q,r : q,r \in \mathbb{Q} , q,r > 0 \}$ such that $$n= qb+r $$ $$0 \le r < b $$

These are some assumptions I have made, but I am unable to solve the problem. $ q \ge 0 $, $b>0$ and $qb \ge 0 $. Also $r \ge 0$ therefore $n= qb+r\ge 0$. Now I have to prove this for a particular solution where $n \ge 1$. Then assuming this true for particular solution where $n$ is $k$ I have to prove this for $k+1$,but I have no idea how to do this. It would be of great help if someone could assist me

1

There are 1 best solutions below

2
On BEST ANSWER

Let $n=0$. The equation $0=0\cdot b+0$ holds true ,so $r=0<b$ and the proposition holds true.
Suppose for $n\in \mathbb{N}$ that $n=qb+r,0\leq r<b$
Then $n+1=qb+r+1$ with $1\leq r+1<b+1$
If $r\leq b-2$ then $r'=r+1<b$.
If $r=b-1$ then $r'=r+1=b$ which means that actually $r'=0$
So $n+1=(q+1)b+0=q'b+r', 0\leq r'<b$.
In both cases the proposition holds true for $n+1$.