Podzielność wyrazu ciągu.

Oddzielone od teorii liczb, proste problemy dotyczące zasad dzielenia itp.
librusss
Użytkownik
Użytkownik
Posty: 12
Rejestracja: 14 paź 2020, o 23:37
Płeć: Mężczyzna
wiek: 20
Podziękował: 3 razy

Podzielność wyrazu ciągu.

Post autor: librusss » 23 paź 2020, o 20:17

Dany jest ciąg: 8, 88, 888, 8888, ...
Mamy określić, czy występuje w nim liczba podzielna przez 2019 (i analogicznie, podzielna przez 2020) - nie ważne jaka jest jej wartość, mamy udowodnić, że takowa po prostu występuje.. Oczywiście można byłoby sprawdzać po kolei czy któryś wyraz ciągu nie dzieli się przypadkiem przez 2019 (rzeczywiście taki jest, znalazłem). Jednak moje pytanie brzmi: czy można dowieść tego innym, elegantszym sposobem?

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15102
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 151 razy
Pomógł: 5009 razy

Re: Podzielność wyrazu ciągu.

Post autor: Premislav » 23 paź 2020, o 20:39

n-ty wyraz tego ciągu daje się opisać wzorem
\(\displaystyle{ a_{n}=8\cdot \frac{10^{n}-1}{9}}\). Mamy \(\displaystyle{ 2019=3\cdot 673}\) i liczby \(\displaystyle{ 3, \ 673}\) są pierwsze, w szczególności są względnie pierwsze. Jeśli więc znajdziemy takie \(\displaystyle{ n}\), że \(\displaystyle{ 673}\) dzieli \(\displaystyle{ 10^{n}-1}\) i \(\displaystyle{ 27}\) dzieli \(\displaystyle{ 10^{n}-1}\) (a więc \(\displaystyle{ 3}\) dzieli \(\displaystyle{ 8\cdot \frac{10^{n}-1}{9}}\)), to żądana podzielność zajdzie.
Dalej sprawę załatwia twierdzenie Eulera (czy jego szczególny przypadek, czyli małe twierdzenie Fermata):
mamy \(\displaystyle{ \varphi(673)=672, \ \varphi(27)=18}\), ponadto \(\displaystyle{ \NWD(10,673)=1, \ \NWD(10, 27)=1}\), zatem dla dowolnego \(\displaystyle{ k\in \NN}\) mamy odpowiednio
\(\displaystyle{ 10^{672k}\equiv 1\pmod{673}, \ 10^{18k}\equiv 1\pmod{27}}\). Mamy \(\displaystyle{ \text{NWW}(18, 672)=2016}\), zatem \(\displaystyle{ 2019}\) dzieli liczbę \(\displaystyle{ a_{2016}=8\cdot \frac{10^{2016}-1}{9}}\).
Nie ma gwarancji, że to najmniejsza taka liczba, pewnie tak nie jest.

Dodano po 5 minutach 46 sekundach:
W zasadzie przyszło mi do głowy mniej techniczne i trochę sprytniejsze rozwiązanie.
Popatrzmy na liczby \(\displaystyle{ a_{1}, a_{2}\ldots a_{2020}}\), gdzie \(\displaystyle{ a_{n}}\) jak wyżej. Reszt z dzielenia przez \(\displaystyle{ 2019}\) jest tylko \(\displaystyle{ 2019}\), więc istnieją wśród nich takie \(\displaystyle{ 1\le i<j\le 2020}\), że \(\displaystyle{ a_{i}\equiv a_{j}\pmod{2019}}\).
Wówczas \(\displaystyle{ a_{j}-a_{i}\equiv 0\pmod{2019}}\), ale zauważmy, że
\(\displaystyle{ a_{j}-a_{i}=\overbrace{8\ldots 8}^{j-i}\overbrace{0\ldots 0}^{i}=10^{i}a_{j-i}}\)
i ponieważ \(\displaystyle{ \NWD\left(10^{i}, 2019\right)=1}\), więc stąd \(\displaystyle{ a_{j-i}\equiv 0\pmod{2019}}\).

librusss
Użytkownik
Użytkownik
Posty: 12
Rejestracja: 14 paź 2020, o 23:37
Płeć: Mężczyzna
wiek: 20
Podziękował: 3 razy

Re: Podzielność wyrazu ciągu.

Post autor: librusss » 24 paź 2020, o 02:09

Premislav pisze:
23 paź 2020, o 20:45
n-ty wyraz tego ciągu daje się opisać wzorem
\(\displaystyle{ a_{n}=8\cdot \frac{10^{n}-1}{9}}\). Mamy \(\displaystyle{ 2019=3\cdot 673}\) i liczby \(\displaystyle{ 3, \ 673}\) są pierwsze, w szczególności są względnie pierwsze. Jeśli więc znajdziemy takie \(\displaystyle{ n}\), że \(\displaystyle{ 673}\) dzieli \(\displaystyle{ 10^{n}-1}\) i \(\displaystyle{ 27}\) dzieli \(\displaystyle{ 10^{n}-1}\) (a więc \(\displaystyle{ 3}\) dzieli \(\displaystyle{ 8\cdot \frac{10^{n}-1}{9}}\)), to żądana podzielność zajdzie.
Dalej sprawę załatwia twierdzenie Eulera (czy jego szczególny przypadek, czyli małe twierdzenie Fermata):
mamy \(\displaystyle{ \varphi(673)=672, \ \varphi(27)=18}\), ponadto \(\displaystyle{ \NWD(10,673)=1, \ \NWD(10, 27)=1}\), zatem dla dowolnego \(\displaystyle{ k\in \NN}\) mamy odpowiednio
\(\displaystyle{ 10^{672k}\equiv 1\pmod{673}, \ 10^{18k}\equiv 1\pmod{27}}\). Mamy \(\displaystyle{ \text{NWW}(18, 672)=2016}\), zatem \(\displaystyle{ 2019}\) dzieli liczbę \(\displaystyle{ a_{2016}=8\cdot \frac{10^{2016}-1}{9}}\).
Nie ma gwarancji, że to najmniejsza taka liczba, pewnie tak nie jest.

Dodano po 5 minutach 46 sekundach:
W zasadzie przyszło mi do głowy mniej techniczne i trochę sprytniejsze rozwiązanie.
Popatrzmy na liczby \(\displaystyle{ a_{1}, a_{2}\ldots a_{2020}}\), gdzie \(\displaystyle{ a_{n}}\) jak wyżej. Reszt z dzielenia przez \(\displaystyle{ 2019}\) jest tylko \(\displaystyle{ 2019}\), więc istnieją wśród nich takie \(\displaystyle{ 1\le i<j\le 2020}\), że \(\displaystyle{ a_{i}\equiv a_{j}\pmod{2019}}\).
Wówczas \(\displaystyle{ a_{j}-a_{i}\equiv 0\pmod{2019}}\), ale zauważmy, że
\(\displaystyle{ a_{j}-a_{i}=\overbrace{8\ldots 8}^{j-i}\overbrace{0\ldots 0}^{i}=10^{i}a_{j-i}}\)
i ponieważ \(\displaystyle{ \NWD\left(10^{i}, 2019\right)=1}\), więc stąd \(\displaystyle{ a_{j-i}\equiv 0\pmod{2019}}\).
Dziękuję za ciekawe rozwiązanie, szczególnie to drugie. Mam jednak prośbę o szczególowsze wyjaśnienie (chcę to dobrze zrozumieć).

Reszt z dzielenia jest rzeczywiście 2019, zatem podajesz wniosek (kongruencja), że \(\displaystyle{ a_{i} - a_{j} }\) (gdzie \(\displaystyle{ 1 \le i < j \le 2020 }\) ) jest podzielne przez 2019. To kluczowy wniosek, bo jak rozumiem dalsze rozważania są zbędne i już na tym można zakończyć dowód istnienia takiej liczby. Stąd moje pytanie, skąd taki wniosek się wziął?

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15102
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 151 razy
Pomógł: 5009 razy

Re: Podzielność wyrazu ciągu.

Post autor: Premislav » 24 paź 2020, o 07:51

Tak, zapis \(\displaystyle{ a_{i}\equiv a_{j}\pmod{2019}}\) oznacza, że \(\displaystyle{ a_{i}}\) daje tę samą resztę, co \(\displaystyle{ a_{j}}\) z dzielenia przez \(\displaystyle{ 2019}\). Reszt z dzielenia przez \(\displaystyle{ 2019}\) jest tylko \(\displaystyle{ 2019}\) (to, mam nadzieję, rozumiesz: ogólnie reszt z dzielenia przez \(\displaystyle{ n\in \NN^{+}}\) jest \(\displaystyle{ n: \left\{0,1\ldots n-1\right\}}\)), a liczb \(\displaystyle{ a_{1}, a_{2}\ldots a_{2020}}\) jest \(\displaystyle{ 2020}\), więc istnieje wśród nich taka reszta, która wystąpi co najmniej dwa razy. Jest to szczególny przypadek bardzo użytecznego faktu, który nazywa się zasadą szufladkową Dirichleta: Zasada szufladkowa Dirichleta
Tak jak to tłumaczyłem mojej siostrze z 4 lata temu: powiedzmy, że w szafie masz trzy pary butów, czyli sześć butów łącznie. Jeśli na chybił-trafił wyciągniesz z tej szafy cztery buty, to masz pewność, że skompletujesz z nich co najmniej jedną parę. Sorry, nie mam czasu tego dłużej tłumaczyć, proponuję przeczytać zalinkowany artykulik na wiki.

librusss
Użytkownik
Użytkownik
Posty: 12
Rejestracja: 14 paź 2020, o 23:37
Płeć: Mężczyzna
wiek: 20
Podziękował: 3 razy

Re: Podzielność wyrazu ciągu.

Post autor: librusss » 24 paź 2020, o 17:42

Premislav pisze:
24 paź 2020, o 07:51
Tak, zapis \(\displaystyle{ a_{i}\equiv a_{j}\pmod{2019}}\) oznacza, że \(\displaystyle{ a_{i}}\) daje tę samą resztę, co \(\displaystyle{ a_{j}}\) z dzielenia przez \(\displaystyle{ 2019}\). Reszt z dzielenia przez \(\displaystyle{ 2019}\) jest tylko \(\displaystyle{ 2019}\) (to, mam nadzieję, rozumiesz: ogólnie reszt z dzielenia przez \(\displaystyle{ n\in \NN^{+}}\) jest \(\displaystyle{ n: \left\{0,1\ldots n-1\right\}}\)), a liczb \(\displaystyle{ a_{1}, a_{2}\ldots a_{2020}}\) jest \(\displaystyle{ 2020}\), więc istnieje wśród nich taka reszta, która wystąpi co najmniej dwa razy. Jest to szczególny przypadek bardzo użytecznego faktu, który nazywa się zasadą szufladkową Dirichleta: Zasada szufladkowa Dirichleta
Spróbowałem analogicznie sprawdzić podzielność któregoś wyrazu tego ciągu przez 2020. Jednakże problem pojawia się przy \(\displaystyle{ NWD(10^j, 2020) }\), ponieważ (wykluczając j = 1 i j = 2) równa się on 20, więc stwierdzenie podzielności \(\displaystyle{ a_{j-i} }\) nie będzie takie łatwe.

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15102
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 151 razy
Pomógł: 5009 razy

Re: Podzielność wyrazu ciągu.

Post autor: Premislav » 24 paź 2020, o 17:58

To prawda, tak ładnie to nie będzie, ale akurat proste rozumowanie wyklucza podzielność \(\displaystyle{ \overbrace{88\ldots 8}^{n}}\) przez \(\displaystyle{ 2020}\). Jeśli jakaś liczba dzieli się przez \(\displaystyle{ 2020=5\cdot 2^{2}\cdot 101}\), to dzieli się też przez \(\displaystyle{ 10}\), ale ostatnia cyfra liczby podzielnej przez \(\displaystyle{ 10}\) jest zerem, a ostatnia cyfra w \(\displaystyle{ \overbrace{88\ldots 8}^{n}}\) jest ósemką, więc podzielność nie zachodzi dla żadnego \(\displaystyle{ n}\).

ODPOWIEDZ