XXV OM - III - Zadanie 3

Niech $ r $ będzie liczbą naturalną. Dowieść, że trójmian $ x^2 - rx - 1 $ nie jest dzielnikiem żadnego wielomianu $ p(x) \neq 0 $ o współczynnikach całkowitych, mniejszych co do wartości bezwzględnej od $ r $.

Rozwiązanie

\spos{1} Przypuśćmy, że wielomian

\[<br />
p(x) = a_0 + a_1x + \ldots + a_nx^n<br />
\]

gdzie $ a_n \ne 0 $, ma współczynniki całkowite, co do wartości bezwzględnej mniejsze od $ r $ i jest podzielny przez trójmian $ f(x) = x^2 - rx - 1 $. Mamy więc

\[<br />
(1) \qquad p = f \cdot h,<br />
\]

gdzie wielomian $ h(x) = b_0 + b_1x + \ldots + b_{n-2}x^{n-2} $ ma współczynniki całkowite, co wynika z algorytmu dzielenia wielomianów.

Porównując odpowiednie współczynniki wielomianów po obu stronach równości (1) otrzymujemy

\[ (2.0) \qquad a_0 = -b_0, \]
\[ (2.1) \qquad a_1 = -b_1-rb_0, \]
\[ (2.2) \qquad a_2 = -b_2 - rb_1 + b_0, \]
\[ \vdots \]
\[ (2.k) \qquad  a_k = -b_k - rb_{k-1} + b_{k-2} \ \textrm{dla} \ k = 2, 3, \ldots,n- 2,\]
\[ \vdots \]
\[ (2.n-2) \qquad a_{n-2} = - b_{n-2} - rb_{n-3} + b_{n-4}, \]
\[ (2.n-1) \qquad a_{n-1} = - rb_{n-2} + b_{n-3}, \]
\[ (2.n) \qquad a_n     = b_{n-2} \]

Z równości (2.n) wynika, że $ b_{n-2} \ne 0 $. Następnie z (2.n - 1) wynika, że $ b_{n-3} \ne 0 $ i liczby $ b_{n-2} $ i $ b_{n-3} $ mają ten sam znak. W przeciwnym razie bowiem mielibyśmy $ |a_{n-1}|  = |-rb_{n-2} + b_{n-3}| = |-rb_{n-2}| + |b_{n-3}| \geq r |b_{n-2}| \geq r $, co przeczy założeniu, że $ |a_{n-1} < r $. Analogicznie z (2.n - 2) otrzymujemy, że $ b_{n-4} \ne 0 $ i liczby $ b_{n-3} $ i $ b_{n-4} $ mają ten sam znak. W przeciwnym razie bowiem mielibyśmy $ |a_{n-2}| = |-b_{n-2} - rb_{n-3} + b_{n-4}| = |-b_{n-2}| + |-rb_{n-3}| + |b_{n-4}| \geq r |b_{n-3}| \geq r| $, co przeczy założeniu, że $ |a_{n-2}| < r $.

Ogólnie, jeżeli dla pewnej liczby $ k \in \{2, 3, \ldots, n - 2\} $ liczby $ b_k $ i $ b_{k-1} $ mają ten sam znak, to $ b_{k-2} \ne 0 $ i liczby $ b_{k-1} $ i $ b_{k-2} $ mają ten sam znak. W przeciwnym razie bowiem z równości (2.k) otrzymalibyśmy, że $ |a_k| = |-b_k| + |-rb_{k-1}|+ |b_{k-2}| \geq r $, co przeczy założeniu.

Na mocy zasady indukcji wynika stąd, że liczby $ b_{n-2}, b_{n-3}, \ldots, b_1, b_0 $ są różne od zera i mają jednakowe znaki. Wobec tego z równości (2.1) otrzymujemy $ |a_1| = |-b_1 -rb_0| = |b_1| + |rb_0| \geq r $, co przeczy założeniu.

Uzyskana sprzeczność dowodzi, że taki wielomian $ p $ nie istnieje.

Uwaga 1. W powyższym rozwiązaniu nie korzystaliśmy w sposób istotny z założenia, że wielomian $ p $ ma współczynniki całkowite. Wystarczyłoby zakładać, że $ |p_n| \geq 1 $ oraz $ |p_i| \leq r - 1 $ dla $ r = 0, 1,\ldots, n-1 $.

Uwaga 2. Niech $ H(f) $ będzie największą wartością bezwzględną współczynników wielomianu $ f $. Dla wielomianów o współczynnikach całkowitych na ogół nie jest prawdą, że jeżeli $ f \mid g $, to $ H(f) \leq H(g) $. Na przykład

\[<br />
(1 - x + x^2)(1 + 2x + x^2) = 1 + x + x^3 + x^4.<br />
\]

Komentarze

Dodaj nową odpowiedź