Strona 1 z 1
Podzielność wyrazu ciągu.
: 23 paź 2020, o 20:17
autor: librusss
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?
Re: Podzielność wyrazu ciągu.
: 23 paź 2020, o 20:45
autor: Premislav
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}}\).
Re: Podzielność wyrazu ciągu.
: 24 paź 2020, o 02:09
autor: librusss
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ął?
Re: Podzielność wyrazu ciągu.
: 24 paź 2020, o 07:51
autor: Premislav
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:
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/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.
Re: Podzielność wyrazu ciągu.
: 24 paź 2020, o 17:42
autor: librusss
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:
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/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.
Re: Podzielność wyrazu ciągu.
: 24 paź 2020, o 17:58
autor: Premislav
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}\).