Problema 10

[Parmenide]

Con il consenso di Fenu, propongo il nuovo problema della maratona.

Dato un intero $n$, definiamo le seguenti funzioni:

$\bullet$ $ \phi(n)$ come il numero di interi positivi $<n$ che sono coprimi con $n$
$\bullet$ $ \sigma(n)$ come la somma di tutti i divisori positivi di $n$
$\bullet$ $ \tau(n)$ come il numero di divisori positivi di $n$, $n$ compreso

Determinare tutti gli interi $n>1$ tali che si ha

$$
\sigma(n)+\phi(n)=n\cdot\tau(n)
$$

[Parmenide]

Lascio un paio di hint per chi volesse provarci, se serve posso pubblicare la soluzione completa

Hint 1:

Testo nascosto:

provare con i numeri da 2 a 13 (o anche qualcuno in più, se volete), e verificate quali risolvono l'equazione. Il claim a questo punto è quasi ovvio

Hint 2:

Testo nascosto:

verificate che le soluzioni del claim verificano, poi si può provare ad ottenere una disuguaglianza stretta per gli altri (bastano stime larghe delle funzioni)

[TheRoS]

D'accordo ci provo io (sperando sia giusta)

Testo nascosto:

Le soluzioni sono i numeri primi.
Ricordiamo un po' di formule considerando $n$ come $\prod_{i=1}^k p_i^{\alpha_i}$ per un certo $k$ naturale. $\phi(n)=\prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1)$ ; $\tau(n)=\prod_{i=1}^k(\alpha_i+1)$; $\sigma(n)=\prod_{i=1}^k (p_i^{\alpha_i+1}-1)/(p_i-1)$. In base a ciò di può riscrivere l'equazione del testo come:
\begin{equation}
\prod_{i=1}^k (p_i^{\alpha_i+1}-1)/(p_i-1)+\prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1)=\prod_{i=1}^k p_i^{\alpha_i}\cdot\prod_{i=1}^k(\alpha_i+1)
\end{equation}
Consideriamo a tal punto la seguente quantità: $\prod_{i=1}^k p_i^{\alpha_i+1}/(p_i-1)+\prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1)$; dimostriamo quindi che questa quantità è minore dell'RHS per $k\geq2$, dimostrando così che l'effettivo l'LHS è minore per quei valori di $k$.
\begin{equation}
\prod_{i=1}^k p_i^{\alpha_i+1}/(p_i-1)+\prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1)=\prod_{i=1}^k p_i^{\alpha_i}\cdot\prod_{i=1}^k(\alpha_i+1)\iff
\end{equation}
\begin{equation}
\iff\prod_{i=1}^k p_i/(p_i-1)+\prod_{i=1}^k (p_i-1)/p_i=\prod_{i=1}^k(\alpha_i+1)
\end{equation}
Notiamo adesso che $\prod_{i=1}^k(\alpha_i+1)$ vale al minimo $2^k$ e che $\prod_{i=1}^k (p_i-1)/p_i$ è minore di 1. La funzione $g(x)=x/x-1$ è decrescente, da cui la funzione $f(k)=2^k-\prod_{i=1}^k p_{o_i}/(p_{o_i}-1)$ è crescente (dove i $p_{o_i}$ sono i primi $k$ primi; non sto a dire perché questa produttoria è massima tra tutti gli insiemi di $k$ primi). Riscriviamoci l'equazione precedente come:
\begin{equation}
\prod_{i=1}^k(\alpha_i+1)-\prod_{i=1}^k p_i/(p_i-1)=\prod_{i=1}^k (p_i-1)/p_i
\end{equation}
L'LHS vale al minimo $f(k)$ e, siccome l'RHS è minore di 1, si ha $f(k)\leq 1$. Siccome $f(k)$ è crescente e $f(2)=1$, sicuramente $k=1$ (più il caso $n=1$).
$n=1$ non funziona. $k=1$ implica che $n$ sia o un primo o una potenza di primo. $n$ primo funziona. $n$ potenza di primo non funziona perché $\prod_{i=1}^k(\alpha_i+1)$ cresce.
Sono consapevole che molti passaggi andrebbero esplicitati con più chiarezza, spero si capisca comunque.

[Parmenide]

Mi sembra che vada bene

[PG93]

Magari più concisamente:

Testo nascosto:

È chiaro che per $n$ non primo $\sigma(n)<1+n+n(\tau(n)-2)$, e $\phi(n)<n-1$. Sommando si ottiene $\sigma(n)+\phi(n)<n\tau(n)$ Perciò vanno bene solo gli $n$ primi.