Zadanie. Pokaż, że każda liczba całkowita \(a\ge 0\) ma dokładnie jeden zapis w układzie pozycyjnym o podstawie \(s>1\).
niby jakiś klasyk ale nie mogę nic wymyśleć, pomożecie ?
system pozycyjny
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Rozumiem, że a i s to liczby naturalne.
Jednoznaczność takiego zapisu wynika z jednoznaczności przedstawienia:
Dla każdej pary liczb naturalnych \(a\ge0\) i \(s>1\) istnieje dokładnie jedna para liczb \(k,\ r\ge0\) takich, że:
\(a=k\cdot s+r\)
gdzie k i r to liczby naturalne i r<s.
Żeby liczbę a zapisać w systemie pozycyjnym o podstawie s, należy:
- znaleźć resztę z dzielenia liczby a przez liczbę s \((r_0)\)
- znaleźć resztę z dzielenia otrzymanego ilorazu przez s \((r_1)\)
- znaleźć resztę z dzielenia otrzymanego poprzednio ilorazu przez s \((r_2)\)
- .
- .
- .
I postępować do czasu, aż iloraz jest równy 0.
Zapisujemy liczbę \(a=r_k\ r_{k-1}r_{k-2}...r_2\ r_1\ r_0\)
Jednoznaczność takiego zapisu wynika z jednoznaczności przedstawienia:
Dla każdej pary liczb naturalnych \(a\ge0\) i \(s>1\) istnieje dokładnie jedna para liczb \(k,\ r\ge0\) takich, że:
\(a=k\cdot s+r\)
gdzie k i r to liczby naturalne i r<s.
Żeby liczbę a zapisać w systemie pozycyjnym o podstawie s, należy:
- znaleźć resztę z dzielenia liczby a przez liczbę s \((r_0)\)
- znaleźć resztę z dzielenia otrzymanego ilorazu przez s \((r_1)\)
- znaleźć resztę z dzielenia otrzymanego poprzednio ilorazu przez s \((r_2)\)
- .
- .
- .
I postępować do czasu, aż iloraz jest równy 0.
Zapisujemy liczbę \(a=r_k\ r_{k-1}r_{k-2}...r_2\ r_1\ r_0\)
tak, to liczby naturalne
ogólnie to wiem jak się znajduje reprezentację liczby przy dowolnej podstawie s, ale ten argument z algorytmem jakoś strasznie do mnie nie trafia... czy to napewno wystarczy, niczego tutaj nie brakuje? nie da się jakoś pokazać tego inaczej? na przykład niewprost zakładając że istnieją dwie reprezentacje i jakoś do sprzeczności sprowadzić?
ogólnie to wiem jak się znajduje reprezentację liczby przy dowolnej podstawie s, ale ten argument z algorytmem jakoś strasznie do mnie nie trafia... czy to napewno wystarczy, niczego tutaj nie brakuje? nie da się jakoś pokazać tego inaczej? na przykład niewprost zakładając że istnieją dwie reprezentacje i jakoś do sprzeczności sprowadzić?
To, co zapisałam, opiera się na twierdzeniu o dzieleniu z resztą.
Dla dowolnych liczb całkowitych a i b, \(b\neq0\), istnieją jednoznacznie określone liczby całkowite q, r, takie, że \(a=qb+r\ \ i\ \ 0\le r<|b|\).
Jeśliby było
\(a=q_1b+r_1=q_2b+r_2,\ \ gdzie\ \ 0\le r_1,\ r_2<|b|,\ \ to\\|(q_1-q_2)b|=|r_1-r_2|<|b|\\|q_1-q_2|=|r_1-r_2|<1\\q_1=q_2 \ i\ \ r_1=r_2\)
Jeśli więc
\(a=r_k\ r_{k-1}...r_2r_1r_0=r'_l\ r'_{l-1}...r'_2r'_1r'_0\)
i
\(a=ps+r_0=ts+r'_0\)
gdzie \(r,\ r'<s\)
to musi być \(p=t\ \ i\ \ r_0=r'_0\)
I analogicznie dalej:
\(k=l\\r_1=r'_1\\r_2=r'_2\\.\\.\\.\\r_k=r'_l\)
Dla dowolnych liczb całkowitych a i b, \(b\neq0\), istnieją jednoznacznie określone liczby całkowite q, r, takie, że \(a=qb+r\ \ i\ \ 0\le r<|b|\).
Jeśliby było
\(a=q_1b+r_1=q_2b+r_2,\ \ gdzie\ \ 0\le r_1,\ r_2<|b|,\ \ to\\|(q_1-q_2)b|=|r_1-r_2|<|b|\\|q_1-q_2|=|r_1-r_2|<1\\q_1=q_2 \ i\ \ r_1=r_2\)
Jeśli więc
\(a=r_k\ r_{k-1}...r_2r_1r_0=r'_l\ r'_{l-1}...r'_2r'_1r'_0\)
i
\(a=ps+r_0=ts+r'_0\)
gdzie \(r,\ r'<s\)
to musi być \(p=t\ \ i\ \ r_0=r'_0\)
I analogicznie dalej:
\(k=l\\r_1=r'_1\\r_2=r'_2\\.\\.\\.\\r_k=r'_l\)