Well-known: determinare ogni n tale che $\phi(n)$ | $n$.

[Sk_Anonymous]

Determinare ogni intero positivo $n$ che sia divisibile per $\phi(n)$, dove $\phi(\cdot)$ denota la funzione di Eulero.

[giuseppe87x]

Vediamo...

$phi(n)|n$ i.e. $EEcinNN$ t.c. $phi(n)c=n$. Dalla moltiplicatività di $phi(n)$ la precendete espressione può essere riscritta come $nc*prod_(p|n)(1-1/p)=n$, con $p$ primo da cui $c((p_(1)-1)*(p_(2)-1)*...*(p_(r)-1))/(p_(1)*p_(2)...*p_(r))=1$, $c=(p_(1)*p_(2)*...*p_(r))/((p_(1)-1)*(p_(2)-1)*...*(p_(r)-1)$. $p_(i)=2$ soddisfa l'uguaglianza come $p_(j)=3$ (in tal caso $p_(j)-1=2$ sarebbe divisibile per $p_(i)$); gli altri fattori al denominatore sono tutti pari e non possono essere divisibili per alcun $p$. Ne viene che gli $n$ per cui la tesi è valida sono quelli nella forma $2^(alpha)*3^(beta)$ per $alpha, beta$ interi non negativi.

[ficus2002]

Anche qui si è parlato di questo problema.

[Sk_Anonymous]

"giuseppe87x":Vediamo...

$phi(n)|n$ i.e. $EEcinNN$ t.c. $phi(n)c=n$. Dalla moltiplicatività di $phi(n)$ la precendete espressione può essere riscritta come $c*prod_(p|n)(1-1/p)=n$, con $p$ primo [...]

Manca un $n$ davanti alla produttoria a primo membro. Tornerò a leggere il resto del tuo intervento sul problema solo quando avrai posto rimedio a quest'errore - altrimenti, mi diventa troppo un casino!

[TomSawyer1]

Allora, si sa che $phi(n)=nprod_(p|n)(1-1/p)$.
$n/(phi(n))=1/(prod_(p|n)((p-1)/p))=prod_(p|n)(p/(p-1))$. Quindi $n$ è dovisibile per $phi(n)$ quando i vari $p-1$ si semplificano con alcuni $p$ del numeratore. Questo è possibile solo se $(p-1)$ divide qualche $p$, cioè quando $n=2^n3^m$, perché solo $3-1$ può dividere solo un primo, cioè $2$.

[Sk_Anonymous]

"Crook":Allora, si sa che $phi(n)=nprod_(p|n)(1-1/p)$.
$n/(phi(n))=1/(prod_(p|n)((p-1)/p))=prod_(p|n)(p/(p-1))$. Quindi $n$ è dovisibile per $phi(n)$ quando i vari $p-1$ si semplificano con alcuni $p$ del numeratore. Questo è possibile solo se $(p-1)$ divide qualche $p$, cioè quando $n=2^n3^m$, perché solo $3-1$ può dividere solo un primo, cioè $2$.

Ma come escludere che $(p-1)$ possa dividere il prodotto di due o più primi? Lo so che pare evidente - in effetti lo è! -, però tagliare corto su certi dettagli tradisce, di tanto in tanto, l'intenzione di nascondersi le piccole difficoltà - che poi sono sempre le peggiori da superare. In questo senso, l'argomento di giuseppe87x - modulo errori - è assai efficace.

[giuseppe87x]

Si, ho dimenticato $n$ davanti la produttoria; in ogni caso $p-1$ è pari, come fa a dividere il prodotto di due o più primi diversi da $2$?
Comunque ho corretto, ma non garantisco niente vista l'ora e...lo spumante

[Sk_Anonymous]

"giuseppe87x":Si, ho dimenticato $n$ davanti la produttoria; in ogni caso $p-1$ è pari, come fa a dividere il prodotto di due o più primi diversi da $2$?

...ma che obiezione è? Tanto per dire, $(31-1)$ | $(2 \cdot 3 \cdot 5 \cdot 7)$.

"giuseppe87x":[...] Dalla moltiplicatività di $phi(n)$ [...], $c=(p_(1)*p_(2)*...*p_(r))/((p_(1)-1)*(p_(2)-1)*...*(p_(r)-1)$ [...]; gli altri fattori al denominatore sono tutti pari e non possono essere divisibili per alcun $p$. [...]

Capisco quel che tenti di fare, giuseppe87x: cerchi di provare che, se $p_i > 3$ per qualche $i = 1, 2, ..., r$, allora esiste un disavanzo di fattori primi fra il numeratore e il denominatore dell'espressione a secondo membro che impedisce alla frazione di assumere un valore intero. L'idea è pregevole, ma dal mio punto di vista è un po' confusa. Al tuo posto, anziché dire che "gli altri fattori al denominatore [...] non possono essere divisibili per alcun $p$", avrei osservato che, se $r \ge 3$ oppure $n$ è dispari, allora $2$ divide il denominatore, ma non il numeratore della frazione, e pertanto $c$ non è un intero. Dunque, a forza, $n$ è pari ed $r \le 2$. Da qui concludere che $n = 2^a \cdot 3^b$, per opportuni $a, b \in NN$, è pressoché immediato. Ad ogni modo, a te valutare se le mie siano considerazioni valide o solamente gravi forme di onanismo mentale...

[giuseppe87x]

"DavidHilbert":[quote="giuseppe87x"]Si, ho dimenticato $n$ davanti la produttoria; in ogni caso $p-1$ è pari, come fa a dividere il prodotto di due o più primi diversi da $2$?

...ma che obiezione è? Tanto per dire, $(31-1)$ | $(2 \cdot 3 \cdot 5 \cdot 7)$.
[/quote]
Ma ho detto primi diversi da $2$, perchè già $2$ è stato semplificato con $3-1$. Se consideri pure $2$ è ovvio che ho detto una cagata.

"DavidHilbert":
[quote="giuseppe87x"][...] Dalla moltiplicatività di $phi(n)$ [...], $c=(p_(1)*p_(2)*...*p_(r))/((p_(1)-1)*(p_(2)-1)*...*(p_(r)-1)$ [...]; gli altri fattori al denominatore sono tutti pari e non possono essere divisibili per alcun $p$. [...]

Capisco quel che tenti di fare, giuseppe87x: cerchi di provare che, se $p_i > 3$ per qualche $i = 1, 2, ..., r$, allora esiste un disavanzo di fattori primi fra il numeratore e il denominatore dell'espressione a secondo membro che impedisce alla frazione di assumere un valore intero. L'idea è pregevole, ma dal mio punto di vista è un po' confusa. Al tuo posto, anziché dire che "gli altri fattori al denominatore [...] non possono essere divisibili per alcun $p$", avrei osservato che, se $r \ge 3$ oppure $n$ è dispari, allora $2$ divide il denominatore, ma non il numeratore della frazione, e pertanto $c$ non è un intero. Dunque, a forza, $n$ è pari ed $r \le 2$. Da qui concludere che $n = 2^a \cdot 3^b$, per opportuni $a, b \in NN$, è pressoché immediato. Ad ogni modo, a te valutare se le mie siano considerazioni valide o solamente gravi forme di onanismo mentale... [/quote]
Hai ragione, sicuramente; comunque anche il mio ragionamento mi sembra corretto quindi boh, forse sarò io affetto da gravi forme di onanismo mentale