$1280000401$ è primo?

[jordan]

Mostrare che $1280000401$ non è primo (senza l'aiuto di calcolatori etc.)

[Troleito br00tal]

Possiamo intanto notare che il numero equivale a $20^7+20^2+1$.

Ma vale $x^7+x^2+1=(1+x+x^2)(x^5-x^4+x^2-x+1)$, di conseguenza $1280000401=20^7+20^2+1=(1+20+20^2)(20^5-20^4+20^2-20+1)$.

[jordan]

Molto bene

Piu' in generale, il fatto è che se p è primo a $\{a_0,a_1,\ldots,a_{p-1}\}$ e' un sistema completo di residui in $\mathbb{Z}/p\mathbb{Z}$ tali che $\min\{a_0,a_1,\ldots,a_{p-1}\}\ge 0$ allora vale la seguente divisione tra polinomi (e in particolare, per tutti gli interi $x$): \[ \sum_{i=0}^{p-1}{x^i} \mid \sum_{i=0}^{p-1}{x^{a_i}} \]

[Drago96]

E questa cosa è dimostrabile più o meno elementarmente?
(se è fattibile preferirei che non postassi la soluzione, al massimo un hint...)

[Troleito br00tal]

Mega hintone:

Testo nascosto:

Complessi.

[Drago96]

Sì, i complessi erano abbastanza telefonati con quel p-esimo ciclotomico...
Boh, per mostrare questa divisibilità mi basta mostrare che tutte le radici del ciclotomico sono anche radici del polinomio a destra; ma questo è piuttosto facile, dato che le radici del ciclotomico sono le radici p-esime primitive dell'unità: sostituendole nel polinomio a destra otteniamo il ciclotomico valutato in una delle sue radici (poiché gli esponenti si riducono modulo p, valutando in una radice p-esima, e sono un sistema completo) e quindi vale 0.
Probabilmente si capisce ben poco, magari poi lo riscrivo per bene...

[jordan]

Se $\alpha$ è una radice di $f(x):=\sum_{i=0}^{p-1}{x^i}$ (i.e. $p(\alpha)=0$), allora anche $f(\alpha)(\alpha-1)=0$. In altre parole, se $\alpha$ è radice di $f(x)$, allora è anche radice di $x^p-1$. Ora, tutte e sole le radici di $x^p-1$ sono $1,\zeta,\zeta^2,\ldots,\zeta^{p-1}$, dove $\zeta$ è una radice primitiva $p$-esima dell'unità. Considerato che $f(1) \neq 0$ e che $\text{deg}(f(x))=p-1$ allora tutte e sole le radici di $f(x)$ sono $\zeta,\zeta^2,\ldots,\zeta^{p-1}$. E' sufficiente quindi verificare che $F(\zeta^i)=0$ per ogni $i=1,2,\ldots,p-1$, dove $F(x):=\sum_{i=0}^{p-1}{x^{a_i}}$. Ma $\{a_0,a_1,\ldots,a_{p-1}\}$ è un sistema completo di residui in $\mathbb{Z}/p\mathbb{Z}$, per cui \[ F(\zeta^j)=\sum_{i=0}^{p-1}{\zeta^{ja_i}}=\sum_{i=0}^{p-1}{\zeta^{ji}}=f(\zeta^j)=0 \implies f(x) \mid F(x) \]