Tételek - Számelmélet - Maradékos osztás

Mondja ki és bizonyítsa a maradékos osztás tételét egész számokra

Tétel: Maradékos osztás tétele

Tetszőleges \(a, b \in \Z\) és \(a, b \ne 0\) egyértelműen létezik \(q, r \in \Z\), hogy

\(a = b \cdot q + r\) és \(0 \le r < |b|\).

Bizonyítás: Maradékos osztás tétele

Ha \(a < b\), akkor \(a = b \cdot \underbrace{0}_{q} + \underbrace{a}_{r}\)

Ha \(a \ge b\), akkor tegyük fel, hogy \(a\)-nál kisebb számok már felírhatóak ilyen alakban.

\(a - b = b \cdot q^{*} + r^{*}\)

\(a = b \cdot q^{*} + b + r^{*}\)

\(a = b \cdot \underbrace{(q^{*} + 1)}_{q} + \underbrace{r^{*}}_{r}\)

\(a = b \cdot q + r = b \cdot q^{*} + r^{*} \quad\) (feltehető, hogy \(r^{*} \ge r\))

\(b \cdot q - b \cdot q^{*} = r^{*} - r\)

\(b \cdot (q - q^{*}) = r^{*} - r\)

Ha \(q \ne q^{*}\), akkor

\(|b \cdot (q - q^{*})| \ge b\;\,\) és \(\;\,|r^{*} - r| < b\)

Ez csak akkor lehet, ha \(q = q^{*}\) és \(r = r^{*}\).