Disuguaglianza "Elementare" della funzione Phi di eulero
Ciao a tutti,
sto incartato da stamattina su un'affermazione che fa il mio libro, ovvero che
"si puo' facilmente mostrare che"
$phi(n) >= sqrt(n) $ per n>6
Bene ho provato a mostrarlo e saro' cretino io, ma sono tre ore che ci sbatto la testa e non ci riesco.
Ho anche cercato su internet la questione, e tutti i siti fanno la stessa affermazione, catalogandola come "diseguaglianza elementare" e non fornendo una dimostrazione.
Io posso pure crederci e fidarmi, ma ho il blocco che se non ho una dimostrazione per ogni affermazione di un libro non riesco a provare ad andare avanti.
Mi dite come si fa per favore, visto che e' tanto facile?
Grazie 1000!
sto incartato da stamattina su un'affermazione che fa il mio libro, ovvero che
"si puo' facilmente mostrare che"
$phi(n) >= sqrt(n) $ per n>6
Bene ho provato a mostrarlo e saro' cretino io, ma sono tre ore che ci sbatto la testa e non ci riesco.
Ho anche cercato su internet la questione, e tutti i siti fanno la stessa affermazione, catalogandola come "diseguaglianza elementare" e non fornendo una dimostrazione.
Io posso pure crederci e fidarmi, ma ho il blocco che se non ho una dimostrazione per ogni affermazione di un libro non riesco a provare ad andare avanti.
Mi dite come si fa per favore, visto che e' tanto facile?
Grazie 1000!
Risposte
Qual è la definizione di $phi(n)$?
si' scusa, ho corretto.
Avevo sbagliato a digitare e non avevo riletto.
Avevo sbagliato a digitare e non avevo riletto.
ok, sono arrivato a una dimostrazione, ma non e' poi cosi' banale:
(scusate se invece degli accenti uso gli apostrofi ma sto con una tastiera finlandese!)
Per la moltiplicativita' della funzione totiente:
$phi(n) = p_1^{i_1 -1}...p_n^{i_n -1}(p_1 -1)...(p_n -1)$
dove $p_1^{i_1}...p_n^{i_n}$ sono i fattori primi di n con i relativi esponenti
devo dimostrare che
$ p_1^{i_1 -1}...p_n^{i_n -1}(p_1 -1)...(p_n -1) >= sqrt(n) = sqrt(p_1^{i_1})...sqrt(p_n^{i_n})$
elevo al quadrato e divido per n
$ \frac{p_1^{i_1}}{p_1^2} ... \frac{p_n^{i_n}}{p_n^2} (p_1 -1)^2 ... (p_n -1)^2 >= 1 $
tutti i $ (p_k -1)^2$ sono maggiori di 1 e se $i_k > 1$ allora $\frac{p_k^{i_k}}{p_k^{2}} >= 1$ per qualunque $p_k$
quindi ci dobbiamo preoccupare solo dei casi in cui $i_k = 1$
in tal caso vado a vedere il valore di $\frac{p_k}{p_k^{2}}(p_k - 1)^2$ cioe' $\frac{1}{p_k}(p_k - 1)^2$
noto che se $p_k >= 3$ questa e' sempre vera. quindi mi devo preoccupare solo del caso che ci sia un fattore primo = 2 con relativo esponente 1 dove in tal caso $\frac{1}{p_k}(p_k - 1)^2 = 1/2$
in tal caso visto che $ n > 6 $ per ipotesi o ha un fattore primo >= 5 o ha un fattore primo 3 con esponente maggiore di 1.
nel caso che abbia un fattore primo >=5 il caso peggiore e' che questo fattore primo abbia esponente 1
allora $1/2 \frac{1}{p_k}(p_k - 1)^2 > 1$ con $p_k >= 5$ a maggior ragione questa disuguaglianza vale se $i_k > 1$
se ha un fattore primo 3 con almeno 2 con esponente $1/2 \frac{3^{2}}{3^2}(p_k - 1)^2 > 1$
Quindi alla fine nella diseguaglianza
$ \frac{p_1^{i_1}}{p_1^{2}}...\frac{p_n^{i_n}}{p_n^{2}}(p_1 -1)^2...(p_n -1)^2 >= 1 $
il membro di sinistra e' un prodotto di espressioni tutte >= 1 e percio' la diseguaglianza e' dimostrata.
Mammamia che faticaccia.
1) e' giusto? mi pare di si'.
2) Visto che tutti i libri affermano che e' elementare, mi sapete mostrare un modo idiota che io non ho visto che aggiri tutto questo ambaradan?
Grazie!^^
odio quando i libri danno le cose come ovvie.
(scusate se invece degli accenti uso gli apostrofi ma sto con una tastiera finlandese!)
Per la moltiplicativita' della funzione totiente:
$phi(n) = p_1^{i_1 -1}...p_n^{i_n -1}(p_1 -1)...(p_n -1)$
dove $p_1^{i_1}...p_n^{i_n}$ sono i fattori primi di n con i relativi esponenti
devo dimostrare che
$ p_1^{i_1 -1}...p_n^{i_n -1}(p_1 -1)...(p_n -1) >= sqrt(n) = sqrt(p_1^{i_1})...sqrt(p_n^{i_n})$
elevo al quadrato e divido per n
$ \frac{p_1^{i_1}}{p_1^2} ... \frac{p_n^{i_n}}{p_n^2} (p_1 -1)^2 ... (p_n -1)^2 >= 1 $
tutti i $ (p_k -1)^2$ sono maggiori di 1 e se $i_k > 1$ allora $\frac{p_k^{i_k}}{p_k^{2}} >= 1$ per qualunque $p_k$
quindi ci dobbiamo preoccupare solo dei casi in cui $i_k = 1$
in tal caso vado a vedere il valore di $\frac{p_k}{p_k^{2}}(p_k - 1)^2$ cioe' $\frac{1}{p_k}(p_k - 1)^2$
noto che se $p_k >= 3$ questa e' sempre vera. quindi mi devo preoccupare solo del caso che ci sia un fattore primo = 2 con relativo esponente 1 dove in tal caso $\frac{1}{p_k}(p_k - 1)^2 = 1/2$
in tal caso visto che $ n > 6 $ per ipotesi o ha un fattore primo >= 5 o ha un fattore primo 3 con esponente maggiore di 1.
nel caso che abbia un fattore primo >=5 il caso peggiore e' che questo fattore primo abbia esponente 1
allora $1/2 \frac{1}{p_k}(p_k - 1)^2 > 1$ con $p_k >= 5$ a maggior ragione questa disuguaglianza vale se $i_k > 1$
se ha un fattore primo 3 con almeno 2 con esponente $1/2 \frac{3^{2}}{3^2}(p_k - 1)^2 > 1$
Quindi alla fine nella diseguaglianza
$ \frac{p_1^{i_1}}{p_1^{2}}...\frac{p_n^{i_n}}{p_n^{2}}(p_1 -1)^2...(p_n -1)^2 >= 1 $
il membro di sinistra e' un prodotto di espressioni tutte >= 1 e percio' la diseguaglianza e' dimostrata.
Mammamia che faticaccia.
1) e' giusto? mi pare di si'.
2) Visto che tutti i libri affermano che e' elementare, mi sapete mostrare un modo idiota che io non ho visto che aggiri tutto questo ambaradan?
Grazie!^^
odio quando i libri danno le cose come ovvie.
Un altro modo è andare per induzione, ma comunque incontri gli stessi problemi che hai incontrato tu. In definitiva non credo ci sia una dimostrazione migliore della tua, ma magari mi sbaglio.
"boulayo":
2) Visto che tutti i libri affermano che e' elementare, mi sapete mostrare un modo idiota che io non ho visto che aggiri tutto questo ambaradan?
Beh, più elementare di così... Tutto ciò che si doveva fare è distinguere dei casi.
Però non ho capito una cosa: perchè $n>6$?
Quella disuguaglianza è verificata anche per $n=5$, $n=4$, $n=3$, $n=1$
Cioè, doveva mettere $n!=6 ^^ n!=2$
Quella disuguaglianza è verificata anche per $n=5$, $n=4$, $n=3$, $n=1$
Cioè, doveva mettere $n!=6 ^^ n!=2$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo