$\sigma (n)+\phi (n)=nd(n) \Leftrightarrow n\in \mathbb{P}$

[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

[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!

[Triarii]

Scusa ma da dopo il secondo punto non è che i tuoi passaggi mi siano molto chiari...
comunque posto la mia intanto

Testo nascosto:

Come hai fatto notare, è facile verificare che se $ n $è primo allora l'espressione è vera.
Dimostriamo ora l'altra freccia. La nostra ipotesi ora è che l'espressione sia vera
LEMMA : i numeri nella forma $ p^a $ non verificano l'ipotesi (con $ a>1 $)
Dimostrazione: L'espressione diventa
$ (1+p+...+p^{a-1}+p^a)+(p^a-p^{a-1})=p^a\cdot (a+1) \Rightarrow 1+p+...p^{a-2}+p^a+p^a=p^a\cdot (a+1) $
Ma $ LHS<RHS $in quanto il primo è formato da $ a+1 $ addendi di cui la maggior parte è minore di $ p^a $, mentre l'altro equivale alla somma di $ (a+1) $addendi uguali a $ p^a $. Questo conclude la dimostrazione del lemma.

Dimostreremo ora che l'espressione non vale per nessun numero composto, che per semplicità sarà nella forma $ n=p^a\cdot q^b $
Sia ora $ LHS=\gamma (n)=\sigma (n)+\phi (n) $. Notiamo che $ \gamma (p^aq^b)=\phi (p^a)\phi (q^b)+\sigma (p^a)\sigma (q^b)=\gamma (p^a)\cdot \gamma (q^b)-[\sigma (p^a)\phi (q^b)+\sigma (q^b)\phi (p^a)] $
Il passaggio è lecito perchè sia $ \phi $ che $ \sigma $ sono funzioni moltiplicative e $ (p^a;q^b)=1 $. Si noti che la quantità fra parentesi quadre è sempre positiva.
Notiamo anche che, grazie ad un ragionamento analogo a prima, $ RHS=p^ad(p^a)\cdot q^bd(q^b) $.
Ma $ LHS<\gamma (p^a) \gamma (q^b)<RHS $, assurdo. Nell'ultimo passaggio abbiamo fatto uso del lemma, applicandolo ad entrambi i $ \gamma $
Questo procedimento può essere esteso anche a numeri composti da più di due primi, a patto di sottrarre a $ LHS $ (cosa che rafforza ulteriormente la nostra catena di disuguaglianze) gli opportuni fattori.
Per essere pignoli si nota che 1 non soddisfa l'uguaglianza. Gli unici $ n $ che quindi soddisfano l'ipotesi sono i primi.