OliForum Matematico

121. (Own) notazioni: Siano $\text{gpf}(x)$ e $\text{lpf}(x)$ il piu' grande fattore primo e il piu' piccolo fattore primo che dividono un intero $x>1$ e $\upsilon_p(x)$ la valutazione p-adica di $x$.
Definiamo infine la funzione aritmetica $f(\cdot):\mathbb{N}_0\to \mathbb{N}_0$ di modo tale che :
$f(n)=1$ se $n=1$ oppure se $\text{gpf}(n)<100$
$f(n)=\text{lpf}\left(n\prod_{p\in \mathbb{P}\cap[1,100]}{p^{-\upsilon_p(n)}}\right)$ altrimenti.

In altre parole, f(n) e' il piu' piccolo primo che divide n, che è maggiore di 100; se tale primo non esiste allora f(n)=1.


Dimostrare che, fissata una costante $C>10^{40}$, esistono infiniti interi positivi $n$ tali che $C<f(n)<f(n+1)<f(n+2)<...<f(n+99)<C^2$.

Ma almeno uno tra $ lpf(n) $, $ lpf(n+1) $ e $ lpf(n+2) $ è uguale a 2... Sbaglio?

Leonida ha scritto:Ma almeno uno tra $ lpf(n) $, $ lpf(n+1) $ e $ lpf(n+2) $ è uguale a 2... Sbaglio?

Una piccola svista, grazie della correzione; con l'occasione, ho reso il problema un po piu' generale..

Seppur e' un risultato che si puo' provare con tecniche "elementari", si puo' prendere "per dato" il postulato di Bertrand..

Lemma: esistono almeno 100 numeri primi $p$ tali che $C < p < C^2$.
Dim.: dimostro per induzione su $k$ che tra $C$ e $2^k C$ vi sono almeno $k$ numeri primi.
Passo base: $k=1$. Segue dal il Teorema di Chebyshef (o Postulato di Bertrand), il quale afferma che esiste almeno un primo tra $C$ e $2C$, purchè $C > 1$.
Passo induttivo: supponiamo esistano $k$ numeri primi tra tra $C$ e $2^k C$. Ancora per il Teorema di Chebyshef, esiste almeno un primo tra $2^k C$ e $2^{k+1} C$, perciò tra $C$ e $2^{k+1} C$ vi sono almeno $k+1$ primi e il passo induttivo è verificato.
In particolare esistono almeno 100 numeri primi $p$ tali che $C < p < 2^{100} C$. Ma $2^{100} C < 8^{34} C < 10^{34} C < 10^{40} C < C^2$ è vera poichè per ipotesi $C > 10^{40}$, da cui segue il Lemma.
Indico con $101 < 103 < ... < p_{C-1} \leq C$ i primi compresi tra 100 e $C$ e con $C < p_{C}< p_{C+1}< ... < p_{C+99} < C^2$ cento numeri primi compresi tra $C$ e $C^2$ (esistono per il Lemma). E' sufficiente scegliere $n$ in modo che risolva il seguente sistema di congruenze:
\[
\left\{
\begin{array}{l}
n \equiv 1 \pmod {101} \\
n \equiv 1 \pmod {103} \\
n \equiv 1 \pmod {...} \\
n \equiv 1 \pmod {p_{C-1}} \\
n +i \equiv 0 \pmod {p_{C +i}}, \forall i, 0 \leq i \leq 99
\end{array}
\right.
\]
Innanzitutto per il Teorema Cinese del Resto esistono infinite soluzioni a questo sistema di congruenze, dato che i moduli sono a due a due coprimi. Inoltre, se $101 \leq p \leq p_{C-1}$, $n +i \equiv i+1 = 1, ... , 100 \not \equiv 0 \pmod p$.
Pertanto $f(n +i) \geq p_{C} > C$, $\forall i, 0 \leq i \leq 99$.
Allora $f(n +i) = p_{C +i}$ ; di conseguenza $f(n) < f(n+1) < ... < f(n +99) < C^2$ è vera perchè lo è $p_C < p_{C +1} < ... < p_{C +99} < C^2$. In conclusione, si ha $C < f(n) < f(n+1) < ... < f(n +99) < C^2$ che è la tesi.
P.S.: dato che questa soluzione è un po' barata, se qualcuno ne ha una che non passi per il Postulato di Bertrand mi sembra giusto cedergli il testimone della staffetta.

Leonida ha scritto:[...]
P.S.: dato che questa soluzione è un po' barata, se qualcuno ne ha una che non passi per il Postulato di Bertrand mi sembra giusto cedergli il testimone della staffetta.

La definirei "barata" solo se hai l'impressione di usare un "cannone" senza un'idea di come si dimostra
In ogni caso, vai avanti, perchè la dimostrazione dell'esistenza di almeno 100 primi nell'intervallo $[C,C^2]$ deve passare da qualche disuguaglianza sulla distribuzione di $\mathbb{P}$, e mi pare questa sia la soluzione piu' naturale..

Visto che sono già 3 giorni che non viene postato il problema 122, si faccia avanti chi vuole