OliForum Matematico

Sia $ n>1 $ un intero composto tale che $ \varphi(n) \mid n-1 $. Mostrare che $ \sigma_1(n)>2009 $.

(Indonesia TST 2009)

Lemma. Se $\varphi(n)\mid n-1$, allora $n$ è libero da quadrati.
Dim. Supponiamo che ci sia un primo $p$ tale che $p^2\mid n$, allora per qualche $\alpha>1$ intero, $p\mid p^{\alpha-1}(p-1)\mid \varphi(n)\mid n-1$, assurdo.

Dimostriamo che $\omega(n)>3$.
$\bullet$ Supponiamo $\omega(n)=2$, ovvero $n=pq$ con $p$ e $q$ primi. Abbiamo che $p-1\mid n-1$ se e solo se $p-1\mid q-1$, infatti $(p-1)q=(n-1)-(q-1)$. Wlog $p-1>q-1$, allora $p-1\not\mid q-1$ e di conseguenza $p-1\not\mid n-1$, ma $(p-1)(q-1)=\varphi(n)\mid n-1$, assurdo.
$\bullet$ Per $\omega(n)=3$, il problema diventa un caso particolare del famoso IMO 1992/1 (che volendo posso dimostrare). Anche in questo caso non ci sono $n$ che soddisfano.

Inoltre $2\not\mid n$, altrimenti $\displaystyle 2\mid \prod_{p\mid n}(p-1)=\varphi(n)\mid n-1=2(n/2)-1$, assurdo.
In conclusione, $\sigma_1(n)\ge\sigma_1(3\cdot 5\cdot 7 \cdot 11)=2304>2009$.

p.s. Ho verificato, e questo problema non è nel TST dell'Indonesia del 2009 (ma è anche probabile che abbia visto male).

In effetti, qua non compare Comunque, la soluzione è giusta