Division mit Rest
1. Satz
Seien \(a,b \in \mathbb{Z}\) mit \(b \neq 0\) Dann gibt es eindeutig bestimmte Zahlen \(q,r \in \mathbb{Z}\) mit:
\begin{align*} a =& q \cdot b + r \\ 0 \leq& r < \vert b\vert \end{align*}2. Beweis
alter beweis, messy :(
2.1. Existenz
2.1.1. \(b > 0\) und \(a \leq 0\)
Sei \(q_1 = 0\) und \(r_1 = a\), sodass gilt
\begin{align*} a =& b \cdot 0 + a \end{align*}Falls \(r_1 < b\) gilt, so ist die Existenz für diesen Fall bewiesen. Sei sonst \(q_2 = q_1 + 1\) und \(r_2 = r_1 - b\), so gilt
\begin{align*} a =& (q_1 + 1) \cdot b + r_1 - b \\ =& q_1 \cdot b + r_1 =& a \end{align*}Da \(b > 0\) gilt, ist auch \(q_1 - b = q_2 < q_1\)
2.1.2. \(b < 0\)
Sei \(b' =& -b\) und \(f' =& -q\). Dann lässt sich der Fall \(b < 0\) auf \(b > 0\) zurückführen mit der Ungleichung
\begin{align*} 0 \leq r < \vert b' \vert \end{align*}auf \(a =& q'b' + r\)
2.1.3. \(a < 0\) und \(b > 0\)
Sei \(a' = -a\) und \(q' = -q -1\) und \(r' = b - r\). Dann gilt
\begin{align*} bq' + r' =& -bq - b + b - r \\ =& -bq - r \\ =& -(b \cdot q + r) \\ =& -a \\ =& a' \end{align*}mit der Ungleichung
\begin{align*} 0 \leq r' < \vert b\vert \end{align*}Somit ist dieser Fall wieder auf den ersten zurückgeführt worden
2.2. Eindeutigkeit
Seien \(r_1,r_2\) mit
\begin{align*} a = q_i b + r_i \end{align*}o.B.d.A. sei \(r_1 \geq r_2\). Dann gilt
\begin{align*} a =& a + a - a \\ =& q_1 b + r_1 + q_1 b + r_1 - q_2 b - r_2 \\ =& (2q_1 - q_2) b + (2r_1 - r_2) \end{align*}wobei \(2r_1 - r_2 \leq r_1\) gilt. Nach der Minimalität von \(r_1\) gilt
\begin{align*} 2r_1 - r_2 = r_1 \end{align*}bzw. \(r_1 = r_2\)