XXXIII OM - I - Zadanie 2

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

Niech $p$ będzie ustaloną liczbą pierwszą. Udowodnić, że liczba

$ \underbrace{11\ldots 1}\underbrace{22\ldots 2}\ldots \underbrace{99\ldots 9} - 123456789 $

dzieli się przez $p$ .

Rozwiązanie

Rozważana liczba $N = 11 \ldots 122 \ldots 2 \ldots 99 \ldots 9 - 123456789$ jest różnicą dwóch liczb, których ostatnimi cyframi są dziewiątki, zatem ostatnią cyfrą liczby $N$ jest zero, liczba ta dzieli się więc przez $2$ oraz przez $5$ , a więc teza jest prawdziwa dla $p = 2$ oraz dla $p = 5$ . Dla $p = 3$ możemy zastosować znaną cechę podzielności liczb całkowitych przez $3$ . Liczba $1 + 2 + \ldots + 9 = 45$ jest podzielna przez $3$ , więc w liczbie $11 \ldots 122 \ldots 2 \ldots 99 \ldots 9$ i w liczbie $123456789$ suma cyfr dzieli się przez $3$ , zatem obie te liczby są podzielne przez $3$ . Stąd wynika, że obie te liczby są podzielne przez $3$ . Liczba $N$ jako ich różnica jest podzielna przez $3$ .

W dalszym rozumowaniu ograniczymy się do przypadku, gdy $p$ jest liczbą pierwszą różną od $2$ , $3$ , $5$ . Ponieważ $11 \ldots 1 = 1 +10+...+ 10^{p-1}= \frac{10^p - 1}{10-1} = \frac{1}{9}(10^p-1)$ , więc daną liczbę $N$ można zapisać w postaci

$ \begin{split} N &= 11 \ldots 1 \cdot (10^{8p} + 2 10^{7p} + \ldots + 8 \cdot 10^p + 9) - (10^8 + 2 \cdot 10^7 + \ldots +8 \cdot 10 + 9) =\\ &= \frac{1}{9} (10^p-1) \cdot \sum_{k=1}^9 k 10^{(9-k)p} - \sum_{k=1}^9 k 10^{(9-k)}=\\ &= \sum_{k=1}^9 k 10^{(9-k)} \left[ \frac{1}{9} (10^p-1)(10^{9-k})^{p-1} -1 \right]=\\ &= \sum_{k=1}^9 k 10^{(9-k)} \frac{1}{9} \left[ 10^p(10^{9-k})^{p-1} -(10^{9-k})^{p-1}-9 \right]=\\ &= \frac{1}{9} \sum_{k=1}^9 k 10^{(9-k)} \{ 10 \cdot \left[ 10^{p-1} (10^{9-k})^{p-1} -1 \right] - [(10^{9-k})^{p-1}-1 ] \}. \end{split} $

Na podstawie twierdzenia Fermata (zob. zadanie przygotowawcze A) stwierdzamy, że następujące liczby

$ lO^{p-1} (10^{9-k})^{p-1} - 1 = (10^{10-k})^{p-1}- 1, $

$ (10^{9-k})^{p-1} - 1 $

są podzielne przez $p$ (istotnie jest tu założenie, że $p \ne 2$ oraz $p \ne 5$ , bo z niego wynika, że $10^{10-k}$ oraz $10^{9-k}$ są liczbami niepodzielnymi przez $p$ ). Wobec tego liczba występująca w nawiasie klamrowym dzieli się przez $p$ , a zatem cała suma w wypisanym wyżej wzorze dzieli się przez $p$ . Ponieważ $p \ne 3$ , więc po podzieleniu tej sumy przez $9$ otrzymamy w dalszym ciągu liczbę podzielną przez $p$ . Udowodniliśmy w ten sposób, że liczba $N$ dzieli się przez $p$ .