Dal treno per Pisa

[Anér]

Dimostrare che $ \lim_{n\rightarrow \infty} \phi (n) =\infty $

[amatrix92]

Uhm ma basta dimostrare che esistono infiniti numeri primi giusto?

[ndp15]

Mi sa che bisogna specificare quali strumenti sono ammessi perchè non è difficile cannoneggiare

[dario2994]

Il problema chiede di dimsotrare che per qualsiasi L intero positivo definitivamente vale $\phi(n)>L$, non che ci sono infiniti valori per cui $\phi(n)>L$

[staffo]

scusa, sicuramente mi sfuggirà qualcosa, ma se dico che, posto p primo, esiste un q tale che $ q>p $, allora per questo q vale $ \phi(q)=q-1 $
e quindi, data appunto l'infinità dei primi, il limite è infinito?

oppure mi sfugge qualcosa...

EDIT: ndp15 editato, si mi sono accorto della castronata =)

[ndp15]

La condizione deve valere per tutti gli $n>N$ con $N$ che puoi scegliere te. Così mostri invece che vale solo per i primi.
Ah edita (nel messaggio ma soprattutto nella tua testa ) il fatto che $\phi(q)=q-2$ se $q$ è primo.

[domx]

Ragazzi, siccome non sono un esperto e siccome mi pare di capire (dal titolo) che è un esercizio dai test della Normale (a cui io aspiro, anche se inutilmente), mi spiegate che vuol dire la phi e l'equazione in generale?

[staffo]

La $ \phi (n) $ indica il numero di interi coprimi con $ n $ minori di $ n $. Non credo affatto sia un esercizio del test della Normale, uno perchè sfogliando i test non lo ho mai notato, due perchè a mio parere richiede conoscenze specifiche in analisi e tdn (dato che non saprei nemmeno a livello concettuale come fare a dimostrare che una roba che non cresce costantemente tende ad infinito)

[domx]

La $ \phi (n) $ indica il numero di interi coprimi con $ n $ minori di $ n $. Non credo affatto sia un esercizio del test della Normale, uno perchè sfogliando i test non lo ho mai notato, due perchè a mio parere richiede conoscenze specifiche in analisi e tdn (dato che non saprei nemmeno a livello concettuale come fare a dimostrare che una roba che non cresce costantemente tende ad infinito)

in poche parole vuole che si dimostri che i numeri coprimi sono infiniti? In effetti sembra quasi impossibile...

[Anér]

No, non è un esercizio di ammissione alla Normale, è un'idea di chi il 25 gennaio scorso si stava recando in treno da Roma a Pisa per partecipare al Winter Camp. Bisogna dimostrare che se si vogliono valori di $ \phi $ grandi almeno 100000000, basta andare abbastanza avanti nella lista dei naturali e prima o poi si arriva ad un numero $ N $ e da $ N $ in poi TUTTI i naturali (e non solo i primi) hanno la $ \phi $ che vale almeno 100000000. Questo deve essere vero anche se al posto di 100000000 metto qualsiasi numero naturale $ k $: da un certo punto in poi la $ \phi $ assume sempre valori maggiori o uguali a $ k $; ovviamente al variare di $ k $ servirà, in generale, cambiare il valore di $ N $ in modo opportuno; se si può sempre fare allora abbiamo dimostrato la tesi. Esistono soluzioni che dando per buono che altre funzioni tendono ad infinito sono completamente elementari.

[Boll]

Il fatto che $ 2^{\varphi(n)}\geq n $ a parte i casi piccoli e stupidi non dovrebbe bastare?

[Anér]

Certo, basterebbe.

[Boll]

Vabè visto che sono vecchio e rincoglionito, direi che quello ve lo lascio, comunque è vero, garantisco io

[Anér]

Volendo è anche vero $ \phi (n) \geq \frac{n}{(\log_2 n) +1} $

[ndp15]

Ci sarebbe anche la più comoda (soprattutto a livello mnemonico) $\phi(n)>\sqrt n$ (sempre modulo casi piccoli). Il problema è che ho l'idea che nessuna di queste sia facilmente dimostrabile.