Pagina 1 di 1

Giocherellando con la $\varphi$

Inviato: 23 ago 2013, 10:29
da scambret
Trovare tutte le coppie $(m,k)$ tali che

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

Re: Giocherellando con la $\varphi$

Inviato: 23 ago 2013, 12:56
da Drago96
Carino! :D
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?

Re: Giocherellando con la $\varphi$

Inviato: 15 set 2013, 12:26
da 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...

Re: Giocherellando con la $\varphi$

Inviato: 15 set 2013, 13:11
da scambret
Non ho ancora trovato una soluzione bella, solo contose. Metteresti anche la tua?? ;)
Anyway, sono quelle :wink:

Re: Giocherellando con la $\varphi$

Inviato: 15 set 2013, 16:25
da Triarii
Probabilmente è sbagliata perchè non uso l'hint di Drago (a meno di non averlo fatto inconsapevolmente :P)
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 :P) la risistemo a modino

Re: Giocherellando con la $\varphi$

Inviato: 19 set 2013, 22:52
da jordan
O146 da Carlein ;)