Proving the Division Algorithm using induction Let $n \in \mathbb{N}$. For every $m \in \mathbb{Z}$, there exist unique $q, r \in \mathbb{Z}$ such that $ m = qn+r$ and $0 \le r \le n-1$. We call $q$ the quotient and $r$ the remainder when dividing into $m$.
I'm having trouble proving this with induction. I believe the idea is to first prove for all $m \in \mathbb{Z} _{\ge 0}$ by induction, then prove for all $m \in \mathbb{Z}$ but $m \notin \mathbb{Z} _{\ge 0}$ using the induction proof on $-m$, since $-m \in \mathbb{N}$.
I'd appreciate any help, thank you.

Base case, $m=0$:$$0=0n+0, 0\le0<n.$$
For any other $q$, we have $qn\le-n\lor qn\ge n$, and as $r=-qn$, $r\ge n\lor r\le-n$, which is not allowed.
Induction, $m\to m+1$:
$$m=qn+r\iff m+1=qn+r+1$$


*

*if $0\le r+1<n$, all conditions are met;

*if $r+1=n$, take $q'=q+1,r'=0$ and $$m+1=q'n+r',0\le r'<n.$$
