Matematyka.pl

Czy istnieje taka liczba postaci \(\displaystyle{ 20072007...200700...0}\), która jest podzielna przez \(\displaystyle{ 2008}\)?

Tak, np.
\(\displaystyle{ 2007 \cdot 10^3 \sum_{k=0}^{11999} 10^{4k}}\), o ile się nie rąbnąłem w obliczeniach (trzy to najmniejsza liczba zer na końcu, dla której nie wali się modulo \(\displaystyle{ 8}\), a potem zostaje wzór na sumę wyrazów ciągu geometrycznego i użeranie się z \(\displaystyle{ 251}\) z użyciem twierdzenia Eulera, wstyd pisać tę całą siłkę).
Mile widziane ładniejsze rozwiązanie.

Premislav pisze: Mile widziane ładniejsze rozwiązanie.

Jakieś jest na pewno, bo to było zadanie z konkursu dla liceum.

mint18 pisze:

Premislav pisze: Mile widziane ładniejsze rozwiązanie.

Jakieś jest na pewno, bo to było zadanie z konkursu dla liceum.

Nie zapominaj, że OM też jest konkursem dla liceum.

A jeśli nie Euler, to chociaż MTF przejdzie? Choć to i tak brzydkie.
Mamy \(\displaystyle{ 2008=8\cdot 251}\) i liczba \(\displaystyle{ 251}\) jest pierwsza.
Zatem by zagwarantować podzielność przez 2008, wystarczy zapewnić podzielność przez \(\displaystyle{ 8}\) i przez \(\displaystyle{ 251}\).
Liczby takie jak z zadania można zapisać w postaci \(\displaystyle{ 10^m \sum_{k=0}^{n}2007 \cdot 10^{4k}}\) dla pewnych \(\displaystyle{ m,n}\) naturalnych.
Gdy \(\displaystyle{ m\ge 3}\), to podzielność przez \(\displaystyle{ 8}\) mamy z głowy. Ponadto\(\displaystyle{ \NWD(251, 10^m 2007)=1}\), bo \(\displaystyle{ 251}\) jest pierwsza oraz \(\displaystyle{ \NWD(251, 2007)=1}\), a także \(\displaystyle{ \NWD(251,10)=1}\). Należy więc się zastanowić, czy istnieje takie \(\displaystyle{ n}\) naturalne, że
\(\displaystyle{ 251 | \sum_{k=0}^{n}10^{4k}}\). Po zwinięciu ze wzoru na sumę wyrazów ciągu geometrycznego mamy
\(\displaystyle{ \sum_{k=0}^{n}10^{4k}= \frac{10000^{n+1}-1}{9999}}\)
Z MTF mamy \(\displaystyle{ 10000^{250}\equiv 1 \pmod{251}}\), więc liczba \(\displaystyle{ 10000^{250}-1}\) dzieli się przez \(\displaystyle{ 251}\), a ponieważ także dzieli się przez \(\displaystyle{ 9999}\) (co bezpośrednio wynika z "niezwartej" formuły lub ze wzoru na różnicę k-tych potęg) oraz liczby \(\displaystyle{ 9999}\) i \(\displaystyle{ 251}\) są względnie pierwsze, to \(\displaystyle{ 251}\) dzieli \(\displaystyle{ \sum_{k=0}^{249}10^{4k}}\) i \(\displaystyle{ 2008}\) dzieli np. liczbę \(\displaystyle{ 1000 \cdot 2007 \sum_{k=0}^{249}10^{4k}}\),
co zresztą potwierdza wolfram.-- 17 wrz 2016, o 00:01 --W zasadzie małe twierdzenie Fermata to szczególny przypadek twierdzenia Eulera, ale ja nie zauważyłem, że mogę tak to uprościć, więc początkowo robiłem bodajże Eulera dla
wykładnika postaci \(\displaystyle{ \phi(251 \cdot \textbf{ coś dużego })}\).

Rozważmy pierwsze 2009 liczb postaci \(\displaystyle{ 2007 \ , \ 20072007 \ , \ 200720072007 \ldots}\) i ich reszty z dzielenia przez \(\displaystyle{ 2008}\). Możliwych reszt jest \(\displaystyle{ 2008}\) a liczb mamy \(\displaystyle{ 2009}\), stąd pewne dwie reszty się powtórzą. Różnica większej i mniejszej jest naszą szukaną liczbą