Niech \(\displaystyle{ k, l, n \in \mathbb{Z}_+}\) i \(\displaystyle{ (k, l)_n = k^n \quad \text{mod }l}\).
Czy dla dowolnego skończonego ciągu \(\displaystyle{ a_b}\) liczb całkowitych dodatnich istnieją takie wartości \(\displaystyle{ k, l}\) że \(\displaystyle{ a_b}\) jest podciągiem \(\displaystyle{ (k, l)_n}\)?
Ciąg reszt z dzielenia
-
Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Ciąg reszt z dzielenia
normalny podciąg czy musi być spójny?
Jeśli musi być spójny to chyba nie da się zrobić ciągu (2,2).
Jesli nie musi być spójny to wystarczy wziąć dużą liczbę pierwszą \(\displaystyle{ p}\) i skorzystać z tego, że grupa \(\displaystyle{ \mathbb{Z}_p^{*}}\) jest cykliczna. To znaczy mniej więcej tyle, że istnieje całkowite \(\displaystyle{ k>0}\) t. że w ciągu \(\displaystyle{ k^n \mbox{ mod }p}\) każda liczba ze zbioru \(\displaystyle{ \{1,2,...,p-1\}}\) powtarza się nieskończenie wiele razy.
Jeśli musi być spójny to chyba nie da się zrobić ciągu (2,2).
Jesli nie musi być spójny to wystarczy wziąć dużą liczbę pierwszą \(\displaystyle{ p}\) i skorzystać z tego, że grupa \(\displaystyle{ \mathbb{Z}_p^{*}}\) jest cykliczna. To znaczy mniej więcej tyle, że istnieje całkowite \(\displaystyle{ k>0}\) t. że w ciągu \(\displaystyle{ k^n \mbox{ mod }p}\) każda liczba ze zbioru \(\displaystyle{ \{1,2,...,p-1\}}\) powtarza się nieskończenie wiele razy.