XXXIV OM - I - Zadanie 6

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Wykazać, że dla dowolnego wielomianu $P$ wielomian $P\circ P \circ P \circ \ldots \circ P(x)-x$ dzieli się przez $P(x)-x$ .

Rozwiązanie

Kładąc $P(x)= a_nx^n + a_{n-1}x^{n-1} + \ldots +a_1x+a_0$ otrzymamy

$ \begin{split} P \circ P(x)-P(x) &= a_n (P(x)^n+- x^n)+ a_{n-1}P(x)^{n-1} + \ldots +a_1P(x)+a_0-\\ &\quad-a_nx^n-a_{n-1}x^{n-1}-\ldots-a_1x-a_0 =\\ &= a_n(P (x)^n-x^n)+ a_{n-1} (P(x)^{n-1} -x^{n-1}) + \ldots + a_1(P(x)- x). \end{split} $

Ponieważ każdy składnik ostatniej sumy można rozłożyć:

$ a_k(P(x)^k-x^k) = a_k(P(x)-x)(P(x)^{k-1} + P(x)^{k-2}x+\ldots+ P(x) \cdot x^{k-2}+ x^{k-1}), $

więc

$ P(x)-x|P \circ P(x)-P(x). $

Podstawiając w ostatniej relacji $P(x)$ w miejsce $x$ otrzymamy $P \circ P(x)-P(x) | P \circ P \circ P(x) - P \circ P(x)$ , skąd na mocy przechodniości relacji podzielności wynika, że $P(x)-x|P \circ P \circ P(x)-P \circ P(x)$ . Stąd dla $k= 1, 2, \ldots$ dostajemy

$ P(x)-x|\underbrace{P \circ P \circ \ldots \circ P}_k (x)- \underbrace{P \circ P \circ \ldots \circ P}_{k-1} (x) $

Wielomian $\underbrace{P \circ P \circ \ldots \circ P}_n (x) - x$ można przedstawić w postaci sumy

$ \begin{split} & \underbrace{P \circ P \circ \ldots \circ P}_n (x)- x = (\underbrace{P \circ P \circ \ldots \circ P}_n(x) - \underbrace{P \circ P \circ \ldots \circ P}_{n-1}(x))+ \\ & + \underbrace{(P \circ P \circ \ldots P}_{n-1}(x)-\underbrace{P \circ P \circ \ldots \circ P}_{n-2}(x))+ \ldots + (P \circ P(x)-P(x))+(P(x)-x) \end{split} $

Na mocy poprzednich rozważań każdy składnik tej sumy dzieli się przez $P(x) - x$ , skąd wynika, że $P(x) - x|\underbrace{P \circ P \circ \ldots \circ P}_n(x) - x$ .