XIII OM - I - Zadanie 5

Zawody matematyczne:

XXIII OM, 1971-1972

Etap:

Dowieść, że wszystkie potęgi liczby, której ośmioma cyframi końcowymi są $12890625$ , mają też na końcu cyfry $12890625$ .

Rozwiązanie

Mamy dowieść, że jeżeli $n$ i $l$ są liczbami całkowitymi, przy czym $n > 0$ , $l \geq 0$ , to

$ (12890625 + 10^8 \cdot l)^n = 12890625 + 10^8 \cdot m, $

gdzie $m$ jest liczbą całkowitą nieujemną.

Zauważmy najpierw, że w rozwinięciu lewej strony powyższej równości według wzoru Newtona dla potęgi dwumianu wszystkie wyrazy z wyjątkiem wyrazu $(12890625)^n$ mają czynnik $108$ . Wyrazy te możemy przenieść na prawą stronę i sprowadzić zadanie do postaci następującej:

Dowieść, że dla każdego naturalnego $n$

$ (1) \qquad (12890625)^n = 12890625 + 10^8 \cdot k_n' $

gdzie $k_n$ jest liczbą całkowitą, zależną oczywiście od $n$ .

Gdy $n = 1$ , wzór (1) jest prawdziwy, $k_1 = 0$ .

Udowodnimy, że wzór (1) jest prawdziwy dla $n = 2$ ; trzeba w tym celu obliczyć kwadrat liczby $12890625$ ; nie potrzeba jednak wyznaczać wszystkich cyfr tego kwadratu, a wystarczy znaleźć tylko $8$ ostatnich. Można na przykład skorzystać z tego, że kwadrat sumy kilku liczb równa się sumie kwadratów tych liczb i podwojonych iloczynów wszystkich par tych liczb i rachować w taki sposób:

$ \begin{split} (1289 & 0625)^2 = (5 + 2 \cdot 10 + 6 \cdot 10^2 + 0 \cdot 10^3 + 9 \cdot 10^4 + 8 \cdot 10^5 + 2 \cdot 10^6 + \\ & + 1 \cdot 10^7)^2 = 25 + 20 \cdot 10 + (60 + 4) 10^2 + 24 \cdot 10^3 + (90 + 36) \cdot 10^4 +\\ & + (80 + 36) \cdot 10^5 + (20 + 32 + 108) \cdot 10^6 + (10 + 8 + 96) \cdot 10^7 + l \cdot 10^8 =\\ & = 5 + 2 \cdot 10 + 6 \cdot 10^2 + 0 \cdot 10^3 + 9 \cdot 10^4 + 8 \cdot 10^5 + 2 \cdot 10^6 + 1 \cdot 10^7 + 10^8 \cdot k_2 = \\ & = 12890625 + 10^8 \cdot k_2. \end{split} $

Jeżeli wzór (1) jest prawdziwy dla pewnej liczby naturalnej $n$ , to jest prawdziwy również dla $n + 1$ , gdyż

$ \begin{split} (12890625)^{n + 1} = (12890625)^n \cdot 12890625 = (12890625)^2 + 10^8 \cdot 12890625 \cdot k_n =\\ = 12890625 + 10^8k_2 + 10^8 \cdot 12890625 \cdot k_n = 12890625 + 10^8 k_{n+1}, \end{split} $

gdzie $k_{n+1} = k_2+ 12890625 k_n$ .

Na podstawie zasady indukcji zupełnej wnioskujemy stąd, że wzór (1) jest prawdziwy dla każdej liczby naturalnej $n$ .

Uwaga. Ciekawa własność liczby $12890625$ , którą poznaliśmy, nasuwa pytanie, czy jest jeszcze więcej liczb o tej samej lub mnej liczbie cyfr, które by miały taką własność. Chodzi zatem o rozwiązanie następującego zagadnienia:

Znaleźć taką liczbę $k$ -cyfrową $A$ , że ostatnie $k$ cyfr każdej potęgi tej liczby tworzą liczbę $A$ .

Tak samo jak w rozwiązaniu poprzednim stwierdzamy, że gdy kwadrat liczby $A$ spełnia warunek zadania, to spełnia je każda potęga tej liczby. Ostatecznie więc zadanie sprowadza się do wyznaczenia takiej $k$ -cyfrowej liczby $A$ , że

$ (2) \qquad A^2 = A + 10^k \cdot m, $

gdzie $m$ jest liczbą całkowitą.

Gdy $k=1$ , rozwiązanie jest natychmiastowe, liczbami poszukiwanymi są $0$ , $1$ , $5$ i $6$ . Wobec tego przyjmiemy w dalszym ciągu, że $k>1$ .

Przypuśćmy, że równość (2) zachodzi dla pewnej liczby naturalnej $k$ -cyfrowej $A$ . Możemy tę równość napisać w postaci

$ (3) \qquad A (A - 1) = 2^k \cdot 5^k \cdot m \ (m = \textrm{liczba naturalna}). $

Liczby $A$ i $A-1$ są pierwsze względem siebie, gdyż każdy wspólny podzielnik tych liczb jest również podzielnikiem ich różnicy równej $1$ , więc takim podzielnikiem jest tylko $1$ lub $-1$ . Ponieważ $A < 10^k$ , więc jedna z tych liczb jest podzielna przez $2^k$ , a druga przez $5^k$ , tzn. możliwe są tylko dwa przypadki:

$ (a) \qquad A = 2^k \cdot x \quad A-1 = 5^k \cdot y \quad (x,y-1 \textrm{ naturalne}) $

$ (b) \qquad A = 5^k \cdot z \quad A - 1 = 2^k \cdot u \quad (z,u - 1 \textrm{ naturalne}). $

W przypadku a)

$ (4) \qquad 2^k \cdot x - 5^k \cdot y = 1, $

a w przypadku b)

$ (5) \qquad 5^k \cdot z - 2^k \cdot u = 1. $

Odwrotnie, jeżeli para liczb naturalnych $(x, y)$ spełnia równanie (4), to liczba $A = 2^k \cdot x$ czyni zadość warunkowi a), zatem również warunkowi (2). Aby liczba ta była rozwiązaniem zadania, trzeba jeszcze żeby miała $k$ cyfr, tzn. żeby był spełniony warunek

$ (6) \qquad 10^{k-1} \leq 2^k \cdot x < 10^k. $

Podobnie, jeżeli para liczb naturalnych $(z, u)$ spełnia równanie (5), to liczba $A = 5^k \cdot z$ jest rozwiązaniem zadania o ile spełnia warunek

$ (7) \qquad 10^{k-1} \leq 5^k \cdot z < 10^k. $

Aby zbadać, czy równania (4) i (5) mają takie rozwiązania, rozpatrzymy ogólnie równanie

$ (8) \qquad ax - by = 1, $

w którym $a$ i $b$ są liczbami całkowitymi, większymi od $1$ i pierwszymi względem siebie.

Udowodnimy, że istnieje jedna i tylko jedna para $(x_0, y_0)$ liczb całkowitych dodatnich spełniających to równanie i warunek $x_0 < b$ . Istotnie, weźmy pod uwagę reszty z dzielenia liczb dodatnich $ax_k - 1$ przez $b$ , gdzie $x_k$ przybiera wartości $1, 2, \ldots, b$ . Wśród tych reszt nie ma równych, gdyby bowiem zachodziły równości

$ ax_1 - 1 = b \cdot q_1 + r, \quad ax_2 - 1 = bq_2 + r, $

gdzie $x_1$ i $x_2$ oznaczają dwie różne liczby spośród liczb $1, 2, \ldots, b$ a $q_1$ i $q_2$ - liczby całkowite, to zachodziłaby równość

$ a (x_1 - x_2) = b (q_1 - q_2), $

zatem liczba $a (x_1 - x_2)$ byłaby podzielna przez $b$ , co jest niemożliwe, gdyż $a$ i $b$ są pierwsze względem siebie a różnica $x_1 - x_2$ jest co do wartości bezwzględnej mniejsza niż $b$ . Jedna z tych $b$ reszt musi być zatem równa $0$ , odpowiednią wartością $x_k$ niech będzie $x_0$ . Liczba $x_0$ nie może być równa $b$ , gdyż $ab - 1$ nie jest podzielne przez $b$ , więc $x_0 < b$ .

Liczbę całkowitą dodatnią $\frac{ax_0 - 1}{b}$ oznaczymy literą $y_0$ , w takim razie

$ (9) \qquad ax_0 - by_0= 1. $

Jeżeli $x$ i $y$ oznaczają dowolne liczby całkowite, spełniające równanie (8), to odejmując równości (8) i (9) otrzymujemy

$ a (x - x_0) = b (y - y_0). $

Ponieważ $a$ i $b$ są pierwsze względem siebie, więc $x - x_0$ jest podzielne przez $b$ , wobec czego $x - x_0 = b \cdot t$ , gdzie $t$ jest liczbą całkowitą, a $y - y_0 = at$ , skąd

$ (10) \qquad x = x_0 + bt, $

$ y = y_0 + at. $

Wszystkie rozwiązania równania (8) w liczbach całkowitych $x$ , $y$ otrzymujemy zatem ze wzorów (10), podstawiając zamiast $t$ liczby całkowite. Liczby te są dodatnie i spełniają warunek $x < b$ wtedy i tylko wtedy, gdy $t = 0$ , tj. gdy $x = x_0$ , $y = y_0$ .

Z powyższego wynika, że istnieje jedna i tylko jedna para liczb całkowitych $(x_0, y_0)$ spełniających równanie (4) i warunki $x_0 > 0$ , $y_0 > 0$ , $x_0 < 5^k$ , wobec czego $A = 2^k \cdot x_0 < 10^k$ ; liczba $A$ jest zatem co najwyżej $k$ -cyfrowa. Może się jednak zdarzyć, że $A$ ma mniej niż $k$ cyfr. Umówimy się, że w takim przypadku dopiszemy z lewej strony $A$ zamiast brakujących cyfr odpowiednią liczbę zer i będziemy uważali, że otrzymaliśmy $k$ -cyfrowe rozwiązanie zadania. Przy takiej umowie zadanie ma dla każdego $k > 1$ jedno rozwiązanie postaci $A = 2^k \cdot x$ ( $x - 1$ naturalna). Analogicznie równanie (5) prowadzi do drugiego rozwiązania postaci $A = 5^k \cdot z$ ( $z - 1$ naturalna).

Na przykład dla $k = 3$ mamy rozwiązania $A_ = 625$ i $A_2 = 376$ , dla $k = 4$ rozwiązaniami są $A_1 = 0625$ i $A_2 = 9376$ , dla $k = 9$ jednym rozwiązaniem jest $A_1 = 212890625$ ; niech czytelnik sam poszuka drugiego rozwiązania. Aby je znaleźć bez długiego rachowania, trzeba się zapoznać z teorią równań nieoznaczonych stopnia pierwszego o $2$ niewiadomych; znajdzie ją czytelnik np. w książkach prof. W. Sierpińskiego Teoria liczb i Arytmetyka teoretyczna.