Tételek - Számelmélet - Számrendszerek
2. Mondja ki és bizonyítsa nemnegatív egész számok adott számrendszerben való felírására vonatkozó tételt
Tétel: Számrendszerek
Legyen \(g \ge 2\) egész szám. Ekkor \(\forall \; n \ge 0\) egész szám egyértelműen felírható az alábbi alakban:
\(n = \sum\limits_{i = 0}^{l} \; d_{i} \cdot g^{i}\)
ahol \(\;d_{i} \in \{0, \;1, \;\dots, \;g - 1\}\).
- \(g\): a számrendszert jelölő szám
- \(d\): a számjegyek
- \(n\): az átváltandó szám
Bizonyítás: Számrendszerek
Létezés (bizonyítás teljes indukcióval)
Ha \(\;0 \le n \le g\,\), legyen \(n = d_0 \;\) (és \(\mathcal{l} = 0\)).
TFH. az állítás igaz egy adott \(n - 1\) értékig.
Ekkor a maradékos osztás tétele szerint legyen
\[n = q \cdot g + r\quad (0 \le r < g)\]
Legyen \(d_0 = r\) és indukció szerint
\[q = d'_0 + d'_1 \cdot g^1 + \dots + d'_m \cdot g^m\]
Ekkor \(\;d_1 = d'_0, \;\;d_2 = d'_1, \;\;\dots \;\;\) és \(\;\mathcal{l} = m + 1\)
Egyértelműség
Legyen
\[n = \sum\limits_{i = 0}^{\mathcal{l}} \, d_i \cdot g^i = \sum\limits_{i = 0}^{\mathcal{l}} \, d'_i \cdot g^i \quad \text{ahol} \;\; d_i > d'_i \ge 0\]
THF.
\[\sum\limits_{i = 0}^{\mathcal{l}} \, d_i \cdot g^i - \pink{d'_{\mathcal{l}} \cdot g^{\mathcal{l}}} = \sum\limits_{i = 0}^{\mathcal{l} - 1} \, d'_i \cdot g^i \quad \text{ahol} \;\; d_i, d'_i > 0, \;\, d_{\mathcal{l}} > 0\]
\[\sum\limits_{i = 0}^{\mathcal{l}} \, d_i \cdot g^i > g^{\mathcal{l}} = 1 + \sum\limits_{i = 0}^{\mathcal{l} - 1} \, (g - 1) \cdot g^i > \sum\limits_{i = 0}^{\mathcal{l} - 1} \, d'_i \cdot g^i\]