XXV OM - III - Zadanie 3

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

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

$ p(x) = a_0 + a_1x + \ldots + a_nx^n $

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

$ (1) \qquad p = f \cdot h, $

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

$ (1 - x + x^2)(1 + 2x + x^2) = 1 + x + x^3 + x^4. $