Tutte le soluzioni della congruenza phi(n) = tau(n) mod n.

[HiTLeuLeR]

Determinare ogni $ n\in\mathbb{N}^+ $ tale che $ \phi(n) \equiv \tau(n) \bmod n $, dove $ \tau(n) $ denota il numero dei divisori interi positivi di n. Qui come al solito, $ \phi(\cdot) $ è la funzione di Eulero.

[Santana]

Determinare ogni $ n\in\mathbb{N}^+ $ tale che $ \phi(n) \equiv \tau(n) \bmod n $, dove $ \tau(n) $ denota il numero dei divisori interi positivi di n. Qui come al solito, $ \phi(\cdot) $ è la funzione di Eulero.

Dalla definizione di $ \phi(n) $ e $ \tau(n) $ sappiamo che queste due sono entrambe $ \leq n $, quindi si tratta di risolvere $ \phi(n)=\tau(n) $. Una disuguaglianza elementare ci dice che $ \phi(n) \geq n^{2/3} $ se $ n>42 $, con il metodo descritto in

http://www.matematicamente.it/f/viewtopic.php?t=8224

e un pò di pazienza si può trovare che $ \tau(n) \leq 3.6974*n^{1/3} $ dove approssimo per non riportare logaritmi vari. Perchè sia $ \phi(n)=\tau(n) $ con $ n>42 $ dovrà essere $ n^{2/3} \leq 3.6974*n^{1/3} $ e infine $ n \leq (3.6974)^3 \leq 51 $ quindi non possono esistere soluzioni per $ n > 51 $ e i restanti casi si provano a mano.

Spero sia corretto, sicuramente non è molto elegante...

[Simo_the_wolf]

Dobbiamo risolvere:

$ p_1^ {\alpha_1} (p_1-1)p_2^ {\alpha_2} (p_2-1)... = (\alpha_1+2)(\alpha_2+2) ... $



definiamo $ f(p,a)= p^a (p-1) / (a+2) $.

Noi dobbiamo avere che $ f(p_1, \alpha_1) f(p_2 , \alpha_2 ) ... =1 $

Se $ p>7 $ allora $ f(p,a) \geq 3 $. Sapendo che $ f(q,a) \geq 1 $ se $ q \neq 2 $ e $ f(2,a) \geq 1/2 $ abbiamo che non possono esserci primi maggiori di $ 5 $

facendo una tabellina con i valori di $ f(p,a) \leq 2 $ otteniamo:

$ f(2,0) = 1/2 $, $ f(2,1)= 2/3 $, $ f(2,2)=1 $ , $ f(2,3)=8/5 $
$ f(3,0)=1 $, $ f(3,1) = 2 $
$ f(5,0)=2 $.

Quindi gli unici n possibili sono: $ 2^3 $ , $ 3 $, $ 2^3 *3 $, $ 2 * 9 $, $ 2*5 $, $ 2*3*5 $.

Quindi 3, 8 , 10 , 18 , 24, 30.

[HiTLeuLeR]

[...] Una disuguaglianza elementare ci dice che $ \phi(n) \geq n^{2/3} $ se $ n>42 $ [...]

Sì, una disuguaglianza elementare, però mai discussa prima su questo forum.

[...] con il metodo descritto in http://www.matematicamente.it/f/viewtopic.php?t=8224 e un pò di pazienza [...]

...quel 3d mi ricorda qualcosa - ma cosa?!

[...] si può trovare che $ \tau(n) \leq 3.6974*n^{1/3} $ [...]. Perchè sia $ \phi(n)=\tau(n) $ con $ n>42 $ dovrà essere $ n^{2/3} \leq 3.6974*n^{1/3} $ e infine $ n \leq (3.6974)^3 \leq 51 $ quindi non possono esistere soluzioni per $ n > 51 $ e i restanti casi si provano a mano.

Tutto questo è orribilmente contoso! è_é

Spero sia corretto, sicuramente non è molto elegante...

Beh, sì... E' corretto... In quanto al resto, preferisco astenermi da ulteriori commenti!

[HiTLeuLeR]

Se $ p>7 $ allora $ f(p,a) \geq 3 $.

Immagino che sia $ p \ge 7 $, dev'esserti sfuggito il segno "=".

Quindi 3, 8 , 10 , 18 , 24, 30.

...e qui ti sei dimenticato la soluzione banale n = 1. La soluzione è comunque corretta.