Polinomio ripetitivo

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
gatto_silvestro
Messaggi: 27
Iscritto il: 20 nov 2010, 17:48

Polinomio ripetitivo

Messaggio da gatto_silvestro » 03 gen 2011, 23:58

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
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Polinomio ripetitivo

Messaggio da dario2994 » 04 gen 2011, 00:07

Intendi $P(P(P(...)))$ oppure $[P(x)]^n$ ?
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Polinomio ripetitivo

Messaggio da jordan » 04 gen 2011, 00:39

La prima..( $ [P(0)]^n $ è costante in $ \mathbb{Z}/p\mathbb{Z} $ ).
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Polinomio ripetitivo

Messaggio da jordan » 04 gen 2011, 02:53

gatto_silvestro ha scritto: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. []
The only goal of science is the honor of the human spirit.

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Re: Polinomio ripetitivo

Messaggio da piever » 04 gen 2011, 15:41

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 $
"Sei la Barbara della situazione!" (Tap)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Polinomio ripetitivo

Messaggio da jordan » 04 gen 2011, 16:09

piever ha scritto:... 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 :mrgreen:
The only goal of science is the honor of the human spirit.

Rispondi