XXIV OM - II - Zadanie 6

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

\[<br /> a_n = 3^n + w(n), n = 0, 1, 2, \ldots .<br /> \]

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

\[<br /> \alpha =<br /> \left[ \frac{r}{2} \right] +<br /> \left[ \frac{r}{4} \right] +<br /> \left[ \frac{r}{8} \right] +<br /> \ldots +<br /> \left[ \frac{r}{2^k} \right],<br /> \]

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

\[<br /> \alpha \leq \frac{r}{2} + \frac{r}{4} + \frac{r}{8} + \ldots + \frac{r}{2^k} =<br /> r \left( 1 - \frac{1}{2^k} \right) < r.<br /> \]

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 $:

\[<br /> \begin{split}<br /> 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} + \\<br /> & + \ldots + 2^n = 1 + 2f_1(n) + 2^2f_2(n) + \ldots + 2^mf_m(n) + 2^{m+1}A,<br /> \end{split}<br /> \]

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

Dla $ n < m $ mamy podobnie:

\[<br /> \begin{split}<br /> 3^n & = (1 + 2)^n =<br /> 1 + 2 \binom{n}{1} + 2^2 \binom{n}{2} + \ldots + 2^n \binom{n}{n} = \\<br /> & = 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),<br /> \end{split}<br /> \]

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

\[<br /> 3^n + f(n) = 3^n + sh(n) = 3^n + ksg(n) = (3^n + g(n)) + (ks - 1) \cdot g(n)<br /> \]

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 $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź