Division Algorithm: Let $a$, $b$ $\in \mathbb{Z}$ be any integers and $b \neq 0$. Then, $\exists$ unique integers $q$, $r$ such that
$a = bq + r$ and $0 \leq r < |b|$.
I am trying to show existence by induction on a, and I need assistance.
This is what I've done so far:
$a=1$: Suppose $a=1$. Then, we can write $1 = b\cdot 0 + 1$. This would be the case when $b>a$, so $0\leq r<|b|$ is satisfied.
Assume true for $a=k$: Suppose that for $k \in \mathbb{Z}$, $b \neq 0$, $\exists q_{k}$, $r_{k}$ s.t. $k = b\cdot q_{k}+r_{k}$ where $0\leq r_{k} < |b|$.
Show true for $a=k+1$: Supposing the case for $a=k$:
$k=b\cdot q_{k}+r_{k}$, where $0\leq r_{k} < |b|$.
Then, $k+1=b\cdot q_{k}+r_{k}+1 \to$ $k+1 = b\cdot q_{k}+(r_{k}+1)$.
If $r_{k}+1 < |b|$, then let $q_{k}=q_{k+1}$, $r_{k+1}=r_{k}+1$, and we're done.
If $r_{k}+1 \geq |b|$, then let $q_{k+1}=q_{k}+1$, until $r_{k+1}<|b|$, and we achieve our desired result.
I was wondering if this proof was correct, and if not, what do I need to do to fix it? Also, do I also need to prove that I can do this:
"If $r_{k}+1 \geq |b|$, then let $q_{k+1}=q_{k}+1$, until $r_{k+1}<|b|$, and we achieve our desired result."
and if so, how do I do that?
Thank you.
You can improve your proof by noting that since $r_k$ is at most $|b| - 1$, that $r_k + 1$ is at most $|b|$ (remember, these are integers we're dealing with, which go up "in increments of $1$").
Thus your second case is just:
$r_k + 1 = |b|$, in which case:
$k+1 = b\cdot q_k + |b|$.
If $b < 0$ take $q_{k+1} = q_k - 1$, if $b > 0$ take $q_{k+1} = q_k + 1$, which shows existence.
This highlights a flaw in your approach: suppose $b = -5$, and $k = 24$.
Now $24 = (-5)(-4) + 4$, so $q_k = -4$ and $r_k = 4$ will work.
However, $k+1 = 25 = (-5)(-4) + 5$, and increasing $q_k$ by $1$ will never work out:
$(-5)(-3)$ INCREASES $r_{k+1}$ to $10$, and it only gets worse as you increase $q_k$:
$(-5)(-2)$ demands an $r_{k+1}$ of $15$
$(-5)(-1)$ requires an $r_{k+1}$ of $20$
$(-5)(0)$ leads to an $r_{k+1}$ of $25$
$(-5)(1)$ leads to a remainder of $30$, and so on.