IMC 2011/3 (polinomi)

[ma_go]

se $p$ è un primo, diciamo che un intero positivo $n$ è $p$-interessante se esistono due polinomi $f,g$ a coefficienti interi tali che $$x^{n}-1 = (x^p-x+1)f(x) + pg(x).$$
a) dimostrare che $p^p-1$ è $p$-interessante.
b) per quali primi $p$, il minimo intero positivo $p$-interessante è $p^p-1$?

[dario2994]

Qui sotto c'è un enorme baco... trovatelo

Faccio la parte a)... riguardo la parte b)... ho solo delle idee ma non riesco proprio a capire come cappero si potrebbe concludere
Sia $Q(x)=x^p-x+1$.
Vale $1\equiv x(1-x^{p-1})\pmod{Q(x)}$
Vale $x^p\equiv x-1 \pmod{Q(x)}$ da cui si ricava facilmente per induzione $x^{p^k}\equiv x-k\pmod{Q(x)}$
Ma allora vale:
$x^{p^p-1}-1\equiv x(1-x^{p-1})(x^{p^p-1}-1)\equiv (1-x^{p-1})(x^{p^p}-x)\equiv (1-x^{p-1})(x-p-x)\equiv p(x^{p-1}-1)\pmod{Q(x)}$
Quindi $p^p-1$ è p-interessante (ponendo $g(x)=x^{p-1}-1$ e $f(x)$ quello che serve).

Per la parte b)... non ho neppure un claim decente, mi verebbe da pensare che sia vero per tutti i primi, ma ho controllato solo per $p=2$... e non mi ci gioco una gamba!
In ogni caso ha un senso lavorare con $x^{k+1}-x$ perchè così posso dire che $k+1$ ha al max p cifre in base $p$. Allora lo scrivo in base $p$ e ottengo:
$\displaystyle p[xg(x)]\equiv x^{k+1}-x\equiv \prod_{i=0}^{p-1}(x-i)^{a_i}-x\pmod{Q(x)}$
Peccato che da qui proprio non riesco ad andare avanti e manco sono convinto sia una strada furba

edit: un'altra possibile idea per la parte b è anche notare che $k$ va bene sse il resto di $x^k-1$ diviso per $x^p-x+1$ deve avere tutti i coef divisibili per $p$.

[dario2994]

Dopo le fantasie del post precedente aggiusto qui, almeno la parte a):
Sia $I=\{(x^p-x+1)A(x)+pB(x)|A,B\in\mathbb{Z}[x]\}$. Dico che dati 2 polinomi $P,Q$ a coef interi vale $P\equiv Q\iff P-Q\in I$.
Quella che ho definito è davvero una relazione di equivalenza e vale anche tutto quello che vorrei che valga (in effetti non so se vale l'annullamento del prodotto... ma tanto non lo uso, ma se vale è una gran figata ) (dimostrarlo è una banalità)
Ora la tesi equivale a mostrare $x^{p^p-1}-1\equiv 0$
Vale (questa volta per davvero) (uso implicitamente il binomio di Newton) $x^{p^{k+1}}=(x^p)^{p^k}\equiv (x-1)^{p^k}\equiv x^{p^k}+(-1)^p$ e da questa se ne ricava: $x^{p^p}\equiv x-p(-1)^p\equiv x$
E quindi come nel post sopra:
$x^{p^p-1}-1\equiv x(1-x^{p-1})(x^{p^p-1}-1)\equiv (1-x^{p-1})(x^{p^p}-x)\equiv 0$
Che è la tesi.

[dario2994]

Altri fatti (per la b) ) che ho pensato senza scriverli quindi hanno ancora più probabilità di essere stronzate:
Nell'equivalenza che ho definito esistono esattamente p^{p} classi. (cioè i polinomi di grado al max p-1 e coefficienti 0,1,... p-1)
Esiste l'inverso di $x$ che è $1-x^{p-1}$ quindi se per $p$ primo l'ordine di $x$ è $p^p-1$ allora $x,x^2,\dots x^{p^p-1}$ sono tutti diversi. (dato che se x è invertibile le potenze sono completamente periodiche)
Vale anche $x^m\not\equiv 0$ (dato che $x$ è invertibile) perciò i valori delle potenze di $x$ dovrebbero essere tutti i polinomi, insomma $x$ è un generatore

[dario2994]

Tra una correzione e l'altra forse sono riuscito a chiudere questo:
Mostro che $\displaystyle x^{\frac{2(p^p-1)}{p-1}}=1$
Bon a voi:
$\displaystyle x^{\frac{2(p^p-1)}{p-1}}\equiv \left(\prod_{i=0}^{p-1}x^{p^i}\right)^2\equiv \left(\prod_{i=0}^{p-1}(x+i(-1)^p)\right)^2\equiv \left(x(x+1)(x+2)\dots (x-(p-1))\right)^2\equiv (x^p-x)^2\equiv (-1)^2$
Quindi se $\frac{2(p^p-1)}{p-1}<p^p-1$ allora $p$ è del tipo di cui parla la tesi. Ma allora $3<p$ implica che $p$ è uno dei primi di cui parla la tesi. Per $p=2$ chiaramente il minore $k$ è $2^2-1=3$.
Per $p=3$... bon deve essere un divisore di $3^3-1=26$ di certo non è $2$, non è 13 perchè 2 righe qui sopra ho dimostrato che $x^{13}\equiv -1$ ma allora è proprio 26
Quindi i primi cui si riferisce la b) sono sono 2,3

p.s. è aperta la caccia all'errore

[dario2994]

Su richiesta dell'autore ho condensato tutto in un solo messaggio, ma mi dispiacerebbe cancellare tutti gli altri che sono molto più istruttivi di questo quindi li lascio.

Il caso $p=2$ è banale e il minor $k$ è proprio $2^2-1=3$ e si può facilmente controllare a mano (magari sfruttando il fatto che il resto di $x^k-1$ modulo $x^2-x+1$ deve avere solo coef divisibili per $p$... è facile mostrare che è equivalente alla richiesta del testo).
Definisco una relazione di equivalenza su $\mathbb{Z[x]}$: $P(x)\equiv Q(x)\iff P(x)-Q(x)\in\{(x^p-x+1)A(x)+pB(x)|A,B\in\mathbb{Z}[x]\}$.
È facile dimostrare che è davvero una relazione di equivalenza e che valgono: $A\equiv B\to A\cdot C\equiv B\cdot C\ \wedge\ A+C\equiv B+C$.

Lemma di Ophelia: $x^{p^k}\equiv x-k$
Dimostro che per induzione su $k$:
Passo base: $k=0$... è ovvio, vale l'identità tra i 2 polinomi.
Passo induttivo: $x^{p^{k+1}}=(x^p)^{p^k}\equiv (x-1)^{p^k}=\sum_{i=0}^{p^k}\binom {p^k}i (-1)^i(x)^{p^k-i}\equiv x^{p^k}-1$
Ora applico l'ipotesi induttiva ed ho il lemma.

Lemma del trist: $x(x-1)(x-2)\dots (x-(p-1))\equiv -1$
È un fatto più o meno noto che $x(x-1)(x-2)\dots (x-(p-1))-(x^p-x)$ ha tutti i coefficienti divisibili per $p$ (altrimenti avrei un polinomio di grado minore di $p$ con $p$ radici mod p-> assurdo).
Inoltre vale banalmente $x^p-x=-1$.
Unendo i 2 fatti, tanto è davvero una relazione d'equivalenza si ottiene il lemma.

Lemma di lui: $\displaystyle x^{\frac{2(p^p-1)}{p-1}}\equiv 1$
Applico uno dopo l'altro il lemma di Ophelia e il lemma del trist:
$\displaystyle x^{\frac{2(p^p-1)}{p-1}}= \left(\prod_{i=0}^{p-1}x^{p^i}\right)^2\equiv \left(\prod_{i=0}^{p-1}(x-i)\right)^2\equiv (-1)^2= 1$

Corollario di lei $\displaystyle x^{p^p-1}\equiv 1$
Per il lemma di lui $x^{\frac{2(p^p-1)}{p-1}}\equiv 1$, elevo da entrambe le parti alla $\frac{p-1}2$ (che è intero dato che $p>2$) e ottengo il corollario.

Allora il corollario di lei è la parte a) per la definizione dell'equivalenza.
Il lemma di lui per $p>3$ trova un $k$ minore di $p^p-1$ per cui tutti i primi maggiori di 3 non rispettano le richieste della parte b).
Il 2 le rispetta e si verifica a mano.
Riguardo al 3... beh se vale $x^k-1\equiv 0$ e $k$ è il minore, dato che $x$ è invertibile (il suo inverso è $1-x^2$), deve anche valere $k|26$ dato che $x^{26}\equiv 1$ (per il corollario di lei). Se per assurdo $k<26$ allora $k\in 1,2,13$. I casi $k=1,2$ si escludono banalmente. Riguardo a $k=13$... beh se guardate con attenzione la dimostrazione del lemma di lui vedete che togliendo quel 2 all'esponente viene $\equiv -1$ e perciò anche 13 falla.
Quindi anche $3$ è uno dei primi cui si riferisce la parte b)

[ma_go]

uppo, giusto per dire che dario2994 non ha esaurito tutte le soluzioni possibili (nonostante la mole di roba postata).

[dario2994]

uppo, giusto per dire che dario2994 non ha esaurito tutte le soluzioni possibili (nonostante la mole di roba postata).

Ma quella postata è giusta?

[EvaristeG]

Mah, visto che siamo in MNE ... Intanto per $p=2$ si fan tutte le verifiche a mano, quindi $p>2$.
$$\mathbb{K}=\mathbb{Z}[x]/(x^p-x+1, p)$$
è il campo di spezzamento di $x^p-x+1$ su $\mathbb{F}_p$ e dunque (poiché quel polinomio è irriducibile mod p) $\mathbb{K}=\mathbb{F}_{p^p}$.
Dunque $G=\mathbb{K}^*$ è un gruppo con $p^p-1$ elementi e per il teorema di (?)Lagrange(?) si ha $g^{|G|}=1$ per ogni $g\in G$. Quindi
$$x^{p^p-1}=1$$
in quanto $x\neq 0$ in $\mathbb{K}$.
Ora, $x^p-x$ si scompone completamente in $\mathbb{F}_p$, quindi $x^p-x=x(x-1)\ldots x(-(p-1))$. D'altra parte, $(a+b)^p=a^p+b^p$ vale in $\mathbb{F}_p$, quindi a maggior ragione in $\mathbb{K}$ che ne è un'estensione.
Quindi $x^{p^k}=(x-1)^{p^{k-1}}=x^{p^{k-1}}-1=x^{p^{k-2}}-1-1=\ldots=x-k$.
Dunque
$$x\cdot x^p\cdot x^{p^2}\cdot\ldots x^{p^{p-1}}=x(x-1)(x-2)\ldots (x-(p-1))=x^p-x=-1$$
Quindi
$$x^{2(p^p-1)/(p-1)}=(-1)^2=1$$
e $p-1>2$ sse $p>3$. Quindi per $3$ si ha che $x^{3^3-1}=x^{26}=1$ ma $x^{13}=-1$.

[dario2994]

Provo a mostrare che $x^p-x+1$ è irriducibile modulo p...
Sia $x^p-x+1\equiv_p A(x)B(x)$ con $A(x)$ irriducibile.
Allora lavoro in $\mathbb{Z}[x]/(A(x),p)$ ma $A(x)$ è irriducibile perciò quello che ho definito è una bella cosa.
In particolare in quello che ho definito ci si scompone completamente A(x) e dato che continua a valere $a^p+b^p=(a+b)^p$ allora se $A(x)=\prod_i (x-\alpha_i)$ allora vale $A(x)=\prod_i (x-\alpha_i)=\prod_i(x-\alpha_i^p)$ (per mostrare l'uguaglianza basta esplicitare i coefficienti della seconda produttoria e vedere che sono uguali a quelli della prima).
Questo mi dice che se $\alpha$ è una radice di $A(x)$ anche $\alpha^p$ lo è. Ma $\alpha$ è radice anche di $x^p-x+1$ e perciò $\alpha^p=\alpha -1$. Quindi $P(\alpha)=0\rightarrow P(\alpha-1)=0$ ma allora le radici di $A(x)$ sono sicuramente almeno queste $\alpha,\alpha-1,\alpha-2,\dots \alpha-(p-1)$ (che sono banalmente distinte) ma sono già $p$ quindi $deg(A)\ge p$ insomma $B(x)$ ha grado 0 e perciò ho mostrato che è irriducibile.

Non escludo che ci sia un modo 1000 volte più facile.
In ogni caso di quello che ho scritto qui sopra non capisco molto quindi:
La scrittura $\mathbb{Z}[x]/(A(x),p)$ vuol dire che aggiungo a $\mathbb{p}$ tutte le radici del polinomio con tutte le potenze necessarie e le combinazioni lineari necessarie?
Perchè "quello che ho definito è una bella cosa"? Nel senso... io non sono riuscito nemmeno a dimostrare, ma poi è il fatto fondamentale, che se aggiungo una radice e le sue potenze varie e le combinazioni lineari allora sei il polinomio è irriducibile le ho aggiunte tutte, cosa che credo sia vera.

Ovviamente se c'è qualcosa che per capirlo mi servono 2 anni di università, o anche "solo" un mese di corso universitario, basta che lo dite e mi metterò il cuore in pace

edit: forse sono riuscito da me ad aggiustare un po' i buchi

[EvaristeG]

E' vero solo quando fai giochetti modulo p ed il motivo è questo:
Esiste un solo campo con $p^k$ elementi.

Ovvero, se $A$ e $B$ sono due insiemi con $|A|=|B|=p^k$ e su entrambi puoi definire somma e prodotto con le usuali proprietà (commutativa, associativa, distributiva) e di modo che, detto $0_A$ (o $0_B$) l'elemento neutro della somma in $A$ (o in $B$), ogni elemento in $A-\{0_A\}$ (o in $B-\{0_B\}$) abbia un inverso moltiplicativo, allora puoi trovare una funzione $f:A\to B$ che rispetta tutte le operazioni e i loro elementi neutri ($f(a+b)=f(a)+f(b)$, $f(ab)=f(a)f(b)$, $f(0_A)=0_B$, $f(1_A)=1_B$). Si dice allora che $A$ e $B$ sono isomorfi come campi.

Inoltre, se un sottocampo $A'$ di un campo $A$ con $|A|=p^k$ è isomorfo a un campo $B$ con $|B|=p^h$, allora $A'$ è l'unico sottocampo di $A$ con quella proprietà (è l'insieme delle soluzioni di $T^{p^h}-T=0$ in $A$).

In alternativa puoi provare a vedere se riesci a dimostrare questo: se $q(x)$ è irriducibile mod p e $\xi\in K=\mathbb{Z}[x]/(q(x), p)$ è tale che $q(\xi)=0$, allora $\xi^{p^j}$ è ancora radice di $q(x)$ per ogni $j$ e se $\xi^{p^h}=\xi$, allora $h=\deg q(x)$, ma non so quanto sia elementare la dimostrazione.

NB: sugli interi è tutto falso ... prendi $\mathbb{Q}$ e fai $\mathbb{Q}[x]/(x^3-2)$, allora è ovvio che questo oggetto si può scrivere come l'insieme dei polinomi a coefficienti in $\mathbb{Q}$ di grado $\leq 2$, con uno strano prodotto (ogni volta che compare $x^3$ sostituisco con $5$). Però
$$\mathbb{Q}(\sqrt[3]{2})\qquad \mathbb{Q}(\sqrt[3]{2}(\cos\pi/3+i\sin\pi/3)$$
sono due campi diversi dentro $\mathbb{C}$ (uno è ordinabile compatibilmente con le operazioni perché contenuto nei reali, l'altro no), ma entrambi corrispondono al campo $\mathbb{Q}[x]/(x^3-2)$.
Il campo che contiene tutte le radici di $x^3-2$ è il più piccolo campo che contiene i due scritti sopra: $\mathbb{Q}(\sqrt[3]{2}, \omega)$, dove $\omega=\cos\pi/3+i\sin\pi/3$.

[dario2994]

In alternativa puoi provare a vedere se riesci a dimostrare questo: se $q(x)$ è irriducibile mod p e $\xi\in K=\mathbb{Z}[x]/(q(x), p)$ è tale che $q(\xi)=0$, allora $\xi^{p^j}$ è ancora radice di $q(x)$ per ogni $j$ e se $\xi^{p^h}=\xi$, allora $h=\deg q(x)$, ma non so quanto sia elementare la dimostrazione.

Ho mostrato che $\xi$ radice implica $\xi^{p^k}$ radice (per dimostrarlo uso sempre la solita roba che $(\sum x_i)^p=\sum x_i^p$ e per ora ovviamente non uso l'irriducibilità) ma non riesco a mostrare che così le becco tutte tutte Continuerò a pensarci

[EvaristeG]

Pensaci qui.