Fattori primi non più grandi di $\sqrt n$

[dario2994]

No!!Neanche tu l'hai capita.Pensare che mi sembrava strano non averla capita.Infatti non si capisce un tubo,lui non definisce niente.Chiama le cose soltanto con k,m,p ecc... non è molto chiara

Ma non è l'unico problema... il fatto grosso è che non capisco proprio la sua idea Forse tenta di strafattorizzare $k^{3m}-1$ usando ciclotomici... ma io ho provato per questa strada ottenendo meno di nulla

[Anér]

Non so se è proprio la stessa cosa di Rust, ma mi pare di sì: se impongo di prendere $ n=k^m $ ho che $ k^{2m}+k^m+1 $ si scompone in un po' di polinomi ciclotomici. Infatti è uguale a $ \frac{k^{3m}-1}{k^m-1} $, ed è perciò il prodotto di tutti i polinomi ciclotomici nella variabile k con indice ogni intero che è divisore di 3m ma non di m. Dando per buono che
1) Il polinomio ciclotomico di indice $ d $ ha grado $ \phi (d) $
2) Se a è un divisore di b allora $ \phi (a)\leq \phi (b) $
3) Se il polinomio monico p(k) ha grado inferiore di m/2 allora per k abbastanza grande $ p(k)<k^{m/2} $
Si ha che se ogni polinomio ciclotomico ha grado minore di m/2 allora fisso m e faccio crescere k in modo che ogni polinomio ciclotomico valga meno di $ k^{m/2} $, e perciò sia divisibile solo per primi minori della radice quadrata di n.
Ora tra tutti i polinomi ciclotomici del prodotto quello con grado maggiore è quello con indice 3m, infatti gli altri hanno indice che divide 3m e quindi grado minore o uguale. Serve trovare m tale che $ \phi (3m)< m/2 $, e questo si trova prendendo $ m=5\cdot 7\cdot 11\cdot 13\cdot \cdots $ con abbastanza primi.
In questo modo si dimostra anche la generalizzazione in cui al posto di $ \sqrt{n} $ mettiamo $ \sqrt[h]{n} $ con h reale positivo.

[dario2994]

Non so se è proprio la stessa cosa di Rust, ma mi pare di sì: se impongo di prendere $ n=k^m $ ho che $ k^{2m}+k^m+1 $ si scompone in un po' di polinomi ciclotomici. Infatti è uguale a $ \frac{k^{3m}-1}{k^m-1} $, ed è perciò il prodotto di tutti i polinomi ciclotomici nella variabile k con indice ogni intero che è divisore di 3m ma non di m. Dando per buono che
1) Il polinomio ciclotomico di indice $ d $ ha grado $ \phi (d) $
2) Se a è un divisore di b allora $ \phi (a)\leq \phi (b) $
3) Se il polinomio monico p(k) ha grado inferiore di m/2 allora per k abbastanza grande $ p(k)<k^{m/2} $
Si ha che se ogni polinomio ciclotomico ha grado minore di m/2 allora fisso m e faccio crescere k in modo che ogni polinomio ciclotomico valga meno di $ k^{m/2} $, e perciò sia divisibile solo per primi minori della radice quadrata di n.
Ora tra tutti i polinomi ciclotomici del prodotto quello con grado maggiore è quello con indice 3m, infatti gli altri hanno indice che divide 3m e quindi grado minore o uguale. Serve trovare m tale che $ \phi (3m)< m/2 $, e questo si trova prendendo $ m=5\cdot 7\cdot 11\cdot 13\cdot \cdots $ con abbastanza primi.
In questo modo si dimostra anche la generalizzazione in cui al posto di $ \sqrt{n} $ mettiamo $ \sqrt[h]{n} $ con h reale positivo.

Sono definitivamente rincoglionito Questa soluzione è fighissima e ridicolizza sia la mia sia il problema stesso

[Anér]

Hai ancora due anni olimpici e mezzo da parte, apprezzerai le soluzioni contorte trovate da solo.