XXIV OM - II - Zadanie 6

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

Udowodnić, że dla każdej liczby całkowitej nieujemnej $m$ istnieje taki wielomian w o współczynnikach całkowitych, że $2^m$ jest największym wspólnym dzielnikiem liczb

$ a_n = 3^n + w(n), n = 0, 1, 2, \ldots . $

Rozwiązanie

Udowodnimy najpierw kilka lematów.

Lemat 1. Dla $r = 1, 2, \ldots$ liczba $2^r$ nie jest dzielnikiem liczby $r!$ .

Dowód. Jak wiadomo (patrz np. W. Sierpiński, Arytmetyka teoretyczna, wyd. 2, 1959, str. 89 lub rozwiązanie zadania 19(1) z XVIII Olimpiady Matematycznej, str. 43), liczba $2$ wchodzi do $r!$ z wykładnikiem

$ \alpha = \left[ \frac{r}{2} \right] + \left[ \frac{r}{4} \right] + \left[ \frac{r}{8} \right] + \ldots + \left[ \frac{r}{2^k} \right], $

gdzie $2^k \leq r < 2^{k+1}$ . Stąd

$ \alpha \leq \frac{r}{2} + \frac{r}{4} + \frac{r}{8} + \ldots + \frac{r}{2^k} = r \left( 1 - \frac{1}{2^k} \right) < r. $

Lemat 2. Jeżeli $k$ jest liczbą nieparzystą, a $t$ - liczbą naturalną, to istnieje taka liczba całkowita $s$ , że liczba $ks - 1$ jest podzielna przez $2^t$ .

Dowód. Z założenia $k = 1 - 2w$ , gdzie $w$ jest pewną liczbą całkowitą. Przyjmując $s = 1 + (2w) + (2w)^2 + \ldots + (2w)^{t-1}$ otrzymamy, że $ks = 1 - (2w)^t$ . Wobec tego liczba $ks - 1$ jest podzielna przez $2^t$ .

Lemat 3. Jeżeli dla pewnego wielomianu $f$ o całkowitych współczynnikach liczba $3^n + f(n)$ jest podzielna przez $2^{m+1}$ dla $n = 0,1, 2, \ldots$ , to wielomian $w(x) = f(x) + 2^m$ ma własność, że największy wspólny dzielnik liczb $a_n = 3^n + w(n)$ , gdzie $n = 0, 1, 2, \ldots$ , jest równy $2^m$ .

Dowód. Z założenia dla $n = 0, 1, 2, \ldots$ istnieje taka liczba całkowita $b_n$ , że $3^n + f(n) = 2^{m+1}b_n$ . Z zadania 3 wiemy, że największy wspólny dzielnik liczb $a_n$ jest potęgą dwójki o całkowitym wykładniku. Ponadto $a_n = 3^n + w(n) = 3^n + f(n) + 2^m = 2^{m+1}b_n + 2^m = 2^m (2b_n + 1)$ . Zatem każda z liczb $a_n$ jest podzielna przez $2^m$ i żadna z nich nie jest podzielna przez $2^{m+1}$ . Wobec tego największy wspólny dzielnik liczb $a_n$ jest równy $2^m$ .

Przystępujemy teraz do rozwiązania zadania. Z lematu 3 wynika, że wystarczy znaleźć taki wielomian $f$ o całkowitych współczynnikach, że każda z liczb $3^n + f(n)$ , gdzie $n = 0, 1, 2, \ldots$ , jest podzielna przez $2^{m+1}$ .

Niech $\displaystyle f_j(x) = \frac{x(x-1) \ldots (x-j+1)}{j!}$ dla $j = 1, 2, \ldots, m$ .

Wtedy $\displaystyle f_j(n) = \binom{n}{j}$ dla $n \geq j$ oraz $f_j(n) = 0$ dla $n = 0, 1, 2, \ldots, j-1$ .

Na mocy wzoru dwumianowego mamy dla $n \geq m$ :

$ \begin{split} 3^n =& (1 + 2)^n = 1 + 2 \binom{n}{1} + 2^2 \binom{n}{2} + \ldots + 2^m \binom{n}{m}+ 2^{m+1} \binom{n}{m+1} + \\ & + \ldots + 2^n = 1 + 2f_1(n) + 2^2f_2(n) + \ldots + 2^mf_m(n) + 2^{m+1}A, \end{split} $

gdzie $A$ jest pewną liczbą całkowitą.

Dla $n < m$ mamy podobnie:

$ \begin{split} 3^n & = (1 + 2)^n = 1 + 2 \binom{n}{1} + 2^2 \binom{n}{2} + \ldots + 2^n \binom{n}{n} = \\ & = 1 + 2f_1(n) + 2^2f_2(n) + \ldots + 2^nf_n(n) + 2^{n+1}f_{n+1}(n) + \ldots + 2^mf_m(x), \end{split} $

ponieważ $f_{n+1}(n) = \ldots = f_m(n) = 0$ .

Zatem wielomian $g(x) = - (1 + 2f_1(x) + 2^2 f_2(x) + \ldots + 2^mf_m (x))$ ma własność, że każda z liczb $3^n + g (n)$ , gdzie $n = 0, 1,2, \ldots$ , jest podzielna przez $2^{m+1}$ . Na ogół jednak współczynniki wielomianu $g$ nie są liczbami całkowitymi.

Z lematu 1 wynika, że współczynniki wielomianu $2^rf_r (x)$ , gdzie $r = 1, 2, \ldots, m$ , są liczbami wymiernymi o nieparzystych mianownikach. Niech $k$ będzie najmniejszym wspólnym mianownikiem wszystkich współczynników wielomianu $g(x)$ . Wtedy $g(x) = \displaystyle \frac{h(x)}{k}$ , gdzie $h (x)$ jest wielomianem o współczynnikach całkowitych. Liczba $k$ jest nieparzysta. Zatem na mocy lematu 2 istnieje taka liczba całkowita $s$ , że $2^{m+1} \mid ks - 1$ .

Wykażemy, że jako wielomian $f(x)$ wystarczy przyjąć $sh(x)$ . Ma on oczywiście współczynniki całkowite. Ponadto dla $n = 0, 1, 2, \ldots$ liczba

$ 3^n + f(n) = 3^n + sh(n) = 3^n + ksg(n) = (3^n + g(n)) + (ks - 1) \cdot g(n) $

jest podzielna przez $2^{m+1}$ , ponieważ $2^{m+1} \mid 3^n + g (n)$ oraz $2^{m+1} \mid ks - 1$ .

Na mocy lematu 3 największy wspólny dzielnik liczb $3^n + f (n) + 2^m$ , gdzie $n = 0, 1, 2, \ldots$ , jest równy $2^m$ , a więc można przyjąć $w(x) =f(x) + 2^m$ .