Polinomio ripetitivo

[gatto_silvestro]

Sia $P(x) = x^3 + 14x^2 − 2x + 1$. Dimostrare che esiste un numero naturale $n$ tale che $\forall x\in \mathbb{Z}$ $101 | P^n(x)-x$

[dario2994]

Intendi $P(P(P(...)))$ oppure $[P(x)]^n$ ?

[jordan]

La prima..( $ [P(0)]^n $ è costante in $ \mathbb{Z}/p\mathbb{Z} $ ).

[jordan]

Sia $P(x) = x^3 + 14x^2 − 2x + 1$. Dimostrare che esiste un numero naturale $n$ tale che $\forall x\in \mathbb{Z}$ $101 | P^n(x)-x$

Sia $ P^{[1]}(x):=P(x) $ e $ P^{[n]}(x):=P^{[n-1]}(P(x)) $ per ogni intero $ n>1 $. Supponiamo per ipotesi che esistano due interi $ 1\le j<i\le 101 $ tale che $ 101\mid P(i)-P(j) $. Allora sarebbe vero che $ 101 \mid (i-j)(i^2+j^2+14i+14j+ij-2) $ $ \implies 101 \mid (i^2+j^2+14i+14j+ij-2) $ $ \implies 101 \mid (2j+14+i)^2-q(i) $ dove $ q(x):=(14+x)^2-4(x^2+14x-2)=-3x^2-28x+204 $. Vediamo che, se $ i $ è fissato allora $ \{2j+14+i\}_{0\le j\le 100} $ è un sistema completo di residui in $ \mathbb{Z}/101\mathbb{Z} $. Per cui il polinomio $ P(x) $ opera iniettivamente in $ \mathbb{Z}/101\mathbb{Z} $ se e solo se $ q(i) $ non è mai un residuo quadratico. Poniamo per assurdo che esista un intero $ i_0 $ tale che $ \left(\frac{q(i_0)}{101}\right)=1 $. Allora:
$ 1=\left(\frac{q(i_0)}{101}\right)=\left(\frac{-1}{101}\right)\left(\frac{q(i_0)}{101}\right)=\left(\frac{3i_0^2+28i_0-2}{101}\right) $$ =\left(\frac{3}{101}\right)\left(\frac{9i_0^2+84i_0-6}{101}\right)=-\left(\frac{(3i_0+14)^2-6-14^2}{101}\right)=-\left(\frac{(3i_0+14)^2}{101}\right)=-1 $, che è una contraddizione. Abbiamo quindi dimostrato che il polinomio $ P(x) $ opera come una funzione bigettiva da $ S $ in $ S $, dove $ S:=\{1,2,\ldots,100,101\} $. Per ogni intero $ l\in S $ sia $ \alpha_l $ il più piccolo intero positivo tale che $ 101\mid P^{[\alpha_l]}(l)-l $. Evidentemente $ n:=\text{lcm}(\alpha_1,\alpha_2,\ldots,\alpha_{101}) $ soddisfa l'ipotesi del problema. []

[piever]

Salve jordan, da quanto tempo anche per me... Non pensavo che ti avrei ancora trovato a imperversare su questo forum

La soluzione chiaramente è giusta, ma c'è una parte che merita di essere detta in modo meno frettoloso, perché per chi è alle prime armi potrebbe essere non ovvia e io la trovo abbastanza interessante:

P(x), essendo una bigezione delle classi di resto modulo 101 (hai fatto vedere che è iniettiva, dunque è anche bigettiva), possiamo interpretarla come una permutazione dei numeri da 1 a 101, vale a dire l'unica permutazione $ \sigma $ per cui $ \sigma(k)\equiv k^3+14k^2-2k+1 \pmod{101} $

Ora l'n che cerchiamo è chiaramente l'ordine di $ \sigma $, che dunque senz'altro esiste finito, inoltre data la permutazione e la sua scrittura in cicli disgiunti è l'mcm delle lunghezze di tali cicli (lo sapevate? sapevatelo!). Nello specifico gli $ \alpha_l $ che dice jordan sono la lunghezza del ciclo in cui si trova $ l $

[jordan]

... inoltre data la permutazione e la sua scrittura in cicli disgiunti è l'mcm delle lunghezze di tali cicli (lo sapevate? sapevatelo!).

Volevo scriverlo, ma era un po' troppo intrecciato da dirlo per bene, e visto che non era necessario ho evitato