[ISL 1992] Somme di potenze

[Talete]

(a) Dimostrare che
\[5^{100}+5^{75}+5^{50}+5^{25}+1\]
non è un numero primo.

(b) Per quali $n$ interi si ha che
\[\sum_{i=0}^{n-1} n^{n^2\cdot i}=n^{n^2\cdot(n-1)}+n^{n^2\cdot(n-2)}+\ldots+n^{n^2}+1\]
non è un numero primo?

[Talete]

Per il punto (a) o per il punto (b)?

Ecco quelli del punto (a) intanto... da usare con cautela perché ognuno è un (grande) passo in avanti verso la soluzione.

Testo nascosto:

Si fattorizza. (Come? Un ciclotomico che si fattorizza?)

Testo nascosto:

Non sperare di fattorizzare $x^4+x^3+x^2+x+1$, devi andare più nello specifico... i ciclotomici non si fattorizzano

Testo nascosto:

Possiamo scrivere $x^4+x^3+x^2+x+1$ come differenza di quadrati? No. Oppure sì?

Testo nascosto:

$x^4+x^3+x^2+x+1=(x^2+3x+1)^2-5x(x+1)^2$. E ora che si fa? Mica è una differenza di quadrati!

Testo nascosto:

$5x$ a volte è un quadrato... ad esempio quando $x=5^{25}$.

Testo nascosto:

Ora è fatta, no? \[5^{100}+5^{75}+5^{50}+5^{25}+1=(5^{50}-5^{38}+3\cdot5^{25}-5^{13}+1)\cdot(5^{50}+5^{38}+3\cdot5^{25}+5^{13}+1).\]

[alegh]

Per non rovinarmi il problema non ho guardato hint. Potresti dirmi se ho scritto qualcosa di utile?

Testo nascosto:

\[
5^{100}+5^{75}+5^{50}+5^{25}+1=(5^{25})^{4}+(5^{25})^{3}+(5^{25})^{2}+5^{25}+1=\dfrac{5^{125}-1}{5^{25}-1}
\]
Pongo $5^{25}=x$
\[
MCD(x^{4}+x^{3}+x^{2}+x+1,x-1)=MCD(x-1,x^{4}+x^{3}+x^{2}+2)=1
\]
Cerco quindi un primo $p$, $p<5^{100}+5^{75}+5^{50}+5^{25}+1$ tale che
\[
\begin{cases}
p\mid 5^{125}-1\\
p\nmid 5^{25}-1
\end{cases}
\qquad\Rightarrow\qquad ord_{p}(5)|125 \qquad ord_{p}(5)\nmid 25
\]
$\Rightarrow$ $ord_{p}(5)=125$ $\Rightarrow$ $125|p-1$ $\Rightarrow$ $p=125k+1$ con $k$ intero positivo pari.
Ora per il teorema di Dirichlet so che esistono infiniti primi della forma $p=125k+1$ ma questo non mi assicura la tesi perché anche $5^{100}+5^{75}+5^{50}+5^{25}+1$ si può scrivere così.

Grazie
P.S. per cosa sta "ISL"? IMO short list?

[Talete]

ISL è IMO ShortList, sì

Testo nascosto:

Sei sicuro vada bene? Non tutti i primi della forma $p=125k+1$ sono tali che $\mathrm{ord}_p(5)\nmid 25$, ad esempio $p=251$. Non so se questo ti possa intralciare, io ho fatto una soluzione completamente diversa... ci penso su e provo a risolverla nel tuo modo, però boh non mi ispira molto... perché dovresti trovare almeno due primi che dividono $5^{125}-1$ e non $5^{25}-1$, giusto?

Boh scusami se non sono molto propositivo ma al momento non mi vengono idee su come continuare la tua soluzione, ma solo come distruggerla

[alegh]

Testo nascosto:

$251$ purtroppo l'avevo trovato anch'io e infatti mi stavo chiedendo se dall'ordine moltiplicativo potessi costruire un primo $p$ tale che $5^{25}-1<p<5^{100}+5^{75}+5^{50}+5^{25}+1$ e con $p=125k+1$, così il problema sarebbe risolto (credo) senza dover trovare due primi come giustamente dicevi tu, ma onestamente credo sia una strada che porterà ad un punto morto.

[Talete]

Testo nascosto:

Giusto, così non servirebbero neanche due primi, ne basta uno con la limitazione $5^{25}<p+1<5^{125}$, come hai giustamente detto.

Hai provato a liftare gli esponenti? Dimostri che tutti i primi che dividono $5^{25}-1$ dividono anche $5^{125}-1$ con lo stesso esponente, giusto? Dunque se quella roba del testo fosse un primo si avrebbe
\[(5^{25}-1)\cdot p=5^{125}-1.\]
Non saprei come concludere da qui però... temo che l'altra soluzione sia l'unica via

[alegh]

Testo nascosto:

Il fatto che se $p^{\alpha}\parallel 5^{25}-1$ allora $p^{\alpha}\parallel 5^{125}-1$ credo sia equivalente a quello che ho fatto ponendo $5^{25}=x$: $5^{100}+5^{75}+5^{50}+5^{25}+1=x^{4}+x^{3}+x^{2}+x+1=\dfrac{x^{5}-1}{x-1}$ ma $MCD(x^{4}+x^{3}+x^{2}+x+1,x-1)=1$ poiché se $p\neq 5$ (caso che posso escludere), se $p|x-1$ $\Rightarrow$ $p\nmid x^{4}+x^{3}+x^{2}+x+1$. Giusto?

[Talete]

Testo nascosto:

Yes, si fa anche con LTE che è più easy, comunque è assolutamente equivalente.
Però da qui non saprei come concludere...

[Talete]

Testo nascosto:

Guardi il problema e escludi una categoria infinita di numeri, giusto?

Testo nascosto:

Ti rimangono i numeri primi. Speri che loro abbiano la magica proprietà per cui $\Phi_p(p^{p^2})$ non è primo.

Testo nascosto:

Ah, ti sarai accorto che quella roba si può scrivere, invece che $\Phi_p(p^{p^2})$, $\Phi_{p^3}(p)$. Facilita i conti ogni tanto, se conosci i ciclotomici.

Testo nascosto:

Bene, poi ti accorgi che $\Phi_8(2)=2^4+1=17$ è primo. E ti rattristi.

Testo nascosto:

$3^{18}+3^9+1=(3^8+3^7-3^6+3^5-3^4+3^3+1)\cdot(3^4+3^3+1)\cdot(3^6-3^5-3^4+3^3+1).$

E questo come l'ho trovato?

Be' almeno so che per $3$ quel robo non è primo, e nemmeno per $5$. E da qui?