Pagina 1 di 1
$\sigma (n)+\phi (n)=nd(n) \Leftrightarrow n\in \mathbb{P}$
Inviato: 25 lug 2013, 16:21
da Triarii
Sia $ \sigma (n) $ la funzione "somma di tutti i divisori positivi di $ n $, $ \phi (n) $ la funzione di Eulero di $ n $ e d(n) la funzione "numero di divisori positivi di $ n $".
Dimostrare che $ \sigma (n)+\phi (n)=nd(n) $ vale se e solo se $ n $ è primo
Re: $ \sigma (n)+\phi (n)=nd(n) \Leftrightarrow n\in \mathbb
Inviato: 29 lug 2013, 19:05
da Gottinger95
Problema molto carino!
Definiamo:
1. \(\displaystyle P(n) := \{ p \in \mathbb{P} \ :\ p \mid n\}\);
2. \(\displaystyle L(n) := \prod_{p \in P(n)}{p}\);
3. \(\displaystyle S(n) := \prod_{p \in P(n)}{(p-1)}\);
4. \(\displaystyle G(n) := \sum_{i=1}^n{\frac{1}{i} } \sim ln(n) \);
5. \(\displaystyle H(n) := \sum_{p \in P(n)}{(p-1)^{-1}}\); notiamo inoltre che \(H(n) \leq G(\omega(n)) \) (in pratica maggioriamo i singoli termini);
6. \(\omega(n) := | P(n) |\).
Innanzitutto il "se" è semplice da verificare: si ha
\( \sigma(p) + \phi(p) =( p+1) + (p-1) = 2p = p d(n) \)
Per il solo se, sfruttiamo queste identità per \(\sigma(n), \phi(n)\) indicando con \(\varphi_p(n)\) la valutazione pi-adica di \(n\):
1. \(\displaystyle \sigma(n) = \sum_{d \mid n}{d} = \prod_{p \in P(n)}{ \sum_{i=0}^{\varphi_p(n)}{p^i} } = \prod_{p \in P(n)}{\frac{p^{\varphi_p(n) + 1} - 1 }{p-1} } = \prod_{p \in P(n)}{(p^{\varphi_p(n) + 1} - 1 ) } \cdot S(n)^{-1} \).
Il passaggio alla produttoria vale perchè ogni divisore può essere espresso come il prodotto di alcuni tra i primi di \(P(n)\) con esponenti minori o uguali alla valutazione pi-adica di \(n\).
2. \(\displaystyle \phi(n) = n \frac{\phi(n)}{n} = n \frac{ S(n)}{L(n)}\), che segue dal fatto che \(\phi(p_1^{\alpha_1} \cdot \ldots \cdot p_k^{\alpha_k}) = \prod_{i=1}^k{p_i^{\alpha_i -1} (p_i-1)}\).
Cerchiamo adesso di usare delle disuguaglianze per capire come deve essere fatto un numero per cui vale l'uguaglianza del testo.
\(\displaystyle d(n) = \frac{\sigma(n) + \phi(n) }{n} = \prod_{p \in P(n)}{(p^{\varphi_p(n) + 1} - 1 )} \cdot \frac{1}{n S(n) } + \frac{ S(n)}{L(n)} \leq \prod_{p \in P(n)}{(p^{\varphi_p(n) + 1})} \cdot \frac{1}{n S(n) }+ \frac{ S(n)}{L(n)} = \frac{n L(n)}{n S(n) }+ \frac{ S(n)}{L(n)} = \frac{L(n)}{S(n)} + \frac{S(n)}{L(n)}\)
Usando l'approssimazione \(1+x < e^x\) (che è precisa per \(x\) abbastanza piccolo), che \(S(n) < L(n) \), e ricordando che \(d(n) = \prod_{p \in P(n)}{(\varphi_p(n) + 1)}\), abbiamo:
\(\displaystyle \prod_{p \in P(n)}{(\varphi_p(n) + 1)} \leq \prod_{p \in P(n)}{( 1+\frac{1}{p-1})} + \left ( \prod_{p \in P(n)}{( 1+\frac{1}{p-1})} \right ) ^{-1} \leq e^{H(n)} + e^{-H(n)} \leq e^{G(\omega(n))} + e^{-G(\omega(n))} \sim e^{ln(\omega(n))} + e^{-ln(\omega(n))} = \omega(n) + \omega^{-1}(n)\)
Notiamo inoltre che \(\prod_{p \in P(n)}{(\varphi_p(n) + 1)} \geq 2^{\omega(n)}\), da cui
\(2^{\omega(n)} \leq \omega(n) + \omega^{-1}(n) \)
che è soddisfatta solo per \(\omega(n) \leq 1\). Per i numeri con \(\omega(n) = 1\), ossia della forma \(p^a\), abbiamo:
\(\displaystyle p^a (a+1) = p^a d(p^a) = \sigma(p^a) + \phi(p^a) = \sum_{i=0}^a{p^i}+p^a-p^{a-1} = \sum_{i=0}^{a-2}{p^i}+ 2p^a\)
Abbiamo \(a+1\) addendi da entrambe le parti, ma nel LHS ci sono \(a-1\) addendi strettamente maggiori dei corrispondenti addendi nel RHS. Perciò \(a>1\) implica \(LHS > RHS\). Questo conclude la dimostrazione.
Scusate se sono stato prolisso, cannonoso, noioso come un libro scolastico e incomprensibile come un bove, ma l'ho scritta un po' di getto, peraltro usando alcuni fatti che avevo giustappunto letto oggi pomeriggio. Se qualcosa non è chiaro, in ogni caso penso che i fatti che ho usato possano essere utili in altri contesti, perciò chiedete pure!
Re: $ \sigma (n)+\phi (n)=nd(n) \Leftrightarrow n\in \mathbb
Inviato: 29 lug 2013, 20:09
da Triarii
Scusa ma da dopo il secondo punto non è che i tuoi passaggi mi siano molto chiari...
comunque posto la mia intanto