Giocherellando con la $\varphi$

[scambret]

Trovare tutte le coppie $(m,k)$ tali che

$$\displaystyle \varphi(\varphi(m^k))=m$$

[Drago96]

Carino!
Anche se come l'ho fatto io è forse un po' contoso...

Hintone (che è l'idea fondamentale per ogni approccio al problema penso):

Testo nascosto:

serve $3-\omega(m)\ge(k-1)\upsilon_2(m)$
Perché? Come si conclude allora? RHS può essere nullo?

[Triarii]

Possibile che le soluzioni siano

Testo nascosto:

(2,3),(4,2) e (1,a) ?
Ho una soluzione forse, ma dire che è brutta è un complimento...

[scambret]

Non ho ancora trovato una soluzione bella, solo contose. Metteresti anche la tua??
Anyway, sono quelle

[Triarii]

Probabilmente è sbagliata perchè non uso l'hint di Drago (a meno di non averlo fatto inconsapevolmente )

Testo nascosto:

I) $ m $è nella forma $ p^a $
Sostituendo otteniamo $ \phi (p^{ak-1}(p-1))=p^a $
Poichè $ (p^{ak-1},(p-1))=1 $, sfruttando la moltiplicatività di $ \phi $ otteniamo $ \phi (p^{ak-1})\phi (p-1)=p $
$ \phi (p-1)<p $ quindi o è uguale a $ 1 $oppure è divisibile per un primo $ q<p $. Quest'ultimo caso è ovviamente assurdo poichè RHS ha come fattore primo solo $ p $.
Quindi $ \phi (p-1)=1\Rightarrow p=2 $
Andiamo quindi a porre $ 2^a=m $nella nostra equazione.
$ \phi (2^{ak-1})=2^a \Rightarrow 2^{ak-2}=2^a \Rightarrow a=1, k=3 $ o $ a=2, k=2 $
L'equazione è quindi soddisfatta da tutti i numeri nella forma $ (2^a;3) $ con a positivo.

II) $ m $è nella forma $ p_1^{a_1}...p_n^{a_n} $ con tutti i primi dispari.
LEMMA: se $ (a,b)\ne 1 $ allora $ \phi (a) \phi (b)<\phi (ab) $
DIM. Svolgendo le phi e semplificando per ab ottengo $ (1-\frac {1} {p_1})...(1-\frac {1} {p_n})<(1-\frac {1} {p_1})...(1-\frac {1} {p_n}) $
Sicuramente a LHS ci sono tutti i fattori primi di $ a $e di $ b $, quelli in comune sono presenti addirittura 2 volte. A RHS invece ci sono meno fattori in quanto i primi di $ a $e $ b $in comune compaiono una ed una sola volta. Poichè ogni fattore è minore stretto di $ 1 $, segue la tesi. (OT: Penso che questo fatto possa essere pure dimostrato con inclusione-esclusione credo...)
Per semplicità suppongo che m abbia solo 2 fattori primi, non dovrebbe essere problematico estenderlo a $ n $di questi.
Sostituendo ottengo $ p_1^{a_1}p_2{a_2}= \phi (p_1^{a_1k-1}(p_1-1)(p_2^{a_2k-1}(p_2-1)>\phi (p_1^{a_1k-1}(p_1-1)) \phi (p_2^{a_2k-2}(p_2-1)=\phi (p_1^{ak-1})\phi (p_2^{ak-1})\phi (p_1-1) \phi (p_2-1)=p_1^{a_1k-2}(p_1-1)p_2^{a_2k-2}(p_2-1) \phi (p_1-1)\phi (p_2-1)>p_1^{a_1}p_2^{a_2} $per $ k\ge 3 $ Assurdo!
In questa catena abbiamo usato nella prima disuguaglianza il lemma, che si poteva utilizzare dato che $ p_1-1 $ e $ p_2-1 $ sotto le nostre ipotesi contenevano entrambi almeno un fattore $ 2 $.

Andiamo ora quindi a vedere che succede se $ k=1 $ o$ k=2 $.
$ k=1 $:
$ \phi (\phi (m))=m $ Assurdo perchè $ \phi (m)<m $ per $ m>1 $

LEMMA 2: $ \phi (4n) è pari $.
DIM. Svolgendo si ottiene $ 2\cdot (roba intera) $ che è palesemente pari.

Torniamo al caso $ k=2 $
Svolgendo otteniamo $ \phi(p_1^{2a_1-1}(p_1-1)p_2^{2a_2-1}(p_2-1)) $ che è nella forma $ \phi(4n) $ visto che $ p_1-1 e p_2-1 $ sono entrambi pari. Dal lemma quindi abbiamo che LHS è pari e RHS no ASSURDO.

Ci resta ora solo il caso in cui $ m=2^{a_1}p_2^{a_2} $ (sempre con $ k=2 $)
Darò uno sketch della dimostrazione. Per prima cosa si dimostra che se un numero è in questa forma ha al più 2 fattori primi (considerando anche il 2).
Svolgendo le due phi otteniamo che deve essere $ p=3 $, altrimenti a sinistra avremmo altri fattori. La prova dei numeri con p=3 non dà soluzioni

Si conclude osservando che $ (1;k) $ sono sempre soluzioni.

Appena ho tempo (e voglia ) la risistemo a modino

[jordan]

O146 da Carlein