XV OM - I - Zadanie 2

Zawody matematyczne:

XV OM, 1963-1964

Etap:

Udowodnić następujące dwie cechy podzielności przez 7:
a) Liczba naturalna $N$ jest podzielna przez 7 wtedy i tylko wtedy, gdy jest podzielna przez 7 liczba $P$ utworzona w taki sposób: pierwszą od lewej strony cyfrę liczby $N$ mnożymy przez 3 i do wyniku dodajemy drugą cyfrę; otrzymaną liczbę mnożymy przez 3 i dodajemy do wyniku trzecią cyfrę itd. aż do wyczerpania wszystkich cyfr.
b) Liczba naturalna $N$ jest podzielna przez 7 wtedy i tylko wtedy, gdy jest podzielna przez 7 liczba $Q$ utworzona w ten sposób, że ostatnią (od lewej strony) cyfrę liczby $N$ mnożymy przez 5, do wyniku dodajemy przedostatnią cyfrę, otrzymaną liczbę mnożymy przez 5 i dodajemy do wyniku trzecią cyfrę od końca itd. aż do wyczerpania wszystkich cyfr.

Rozwiązanie

Niech $a_0, a_1, \ldots, a_n$ oznaczają kolejne cyfry liczby $N$ (od lewej strony). Wówczas

$ N = a_0 \cdot 10^n + a_1 \cdot 10^{n-1} + \ldots + a_{n-1} \cdot 10 + a_n. $

a) Według tekstu zadania liczba $P$ jest $(n+1)$ -szą liczbą ciągu

$ P_0 = a_0,\ P_1 = a_0 \cdot 3 + a_1,\ P_2 = [a_0 \cdot 3 + a_1) \cdot 3 + a_2 = a_0 \cdot 3^2 + a_1 \cdot 3 + a_2, \ldots \textrm{itd.} $

zatem

$ P = P_n = a_0 \cdot 3^n + a_1 \cdot 3^{n-1} + \ldots + a_{n-1} \cdot 3 + a_n. $

Wobec tego

$ (1) \qquad N- P = a_0 (10^n-3^n) + a_1 (10^{n-1} - 3^{n-1}) + \ldots + a_{n-1} (10-3). $

Ponieważ dla naturalnego $k$

$ 10^k - 3^k = (10-3) (10^{k-1} + 10^{k-2} \cdot 3 + \ldots + 3^{k-1}), $

więc każdy wyraz prawej strony równości (1) jest podzielny przez $7$ . Liczba $N - P$ jest zatem podzielna przez $7$ , skąd wynika, że $N$ jest podzielne przez $7$ wtedy i tylko wtedy, gdy $P$ jest podzielne przez $7$ .

b) Liczba $Q$ jest liczbą ciągu

$ Q_0 = a_n,\ Q_1 = a_n \cdot 5 + a_{n-1} $

$ Q_2 = (a_n \cdot 5 + a_{n-1}) \cdot 5 + a_{n-2} = a_n \cdot 5^2 + a_{n-1} \cdot 5 + a_{n-2} $

zatem

$ Q = a_n \cdot 5^n + a_{n-1} \cdot 5^{n-1} \ldots + a_1 \cdot 5 + a_0. $

Otóż

$ N \cdot 5^n = a_0 \cdot 50^n + a_1 \cdot 5 \cdot 50^{n-1} + \ldots + a_{n-1} \cdot 5^{n-1} \cdot 50 + a_n \cdot 5^n $

więc

$ (2) \qquad N \cdot 5^n - Q = a_0 (50^n - 1) + a_1 \cdot 5 (50^{n-1}- 1) + \ldots + + a_{n-1} \cdot 5^{n-1} (50-1). $

Ponieważ dla naturalnego $k$ liczba $50^k -1$ jest podzielna przez $50 - 1 = 49$ , a tym samym przez $7$ , więc z równości (2) wynika, że liczba $N \cdot 5^n-Q$ jest podzielna przez $7$ . Zatem liczby $N \cdot 5^n$ i $Q$ , i tak samo liczby $N$ i $Q$ są bądź obie podzielne przez $7$ , bądź obie niepodzielne przez $7$ .