Problema 4 "Perdono condizionato"

[Sdavas]

Ho preso in esame il problema 4 della finale di Cesenatico sezione pubblico:

"Eigen Man ha deciso che perdonerà Capitan Numerica solo se quest’ultimo risolverà il quesito seguente. Sia p
un primo positivo per cui esistono m,n interi tali che p | m, φ(m) | n, e φ(n) | m, dove φ indica la funzione φ di Eulero".

E' facile verificare il caso in cui p=2
m=16 φ(m)=8
n=8 φ(n)=4

e p=3
m=18 φ(m)=6
n=54 φ(n)=18

Non sono però riuscito a trovare altri primi per i quali valga la relazione indicata nel testo.
Ho considerato il caso in cui n è multiplo di φ(n), ma prendendo qualsiasi numero primo, nella funzione di Eulero compaiono dei fattori che non sono presenti nel numero di partenza.
Ad esempio se n=5k, in φ(5k) compare almeno una potenza di 2 in più rispetto a n.

Ringrazio subito chi vuole cimentarsi nella risoluzione del problema.

[j18eos]

"RobStam":[...] "Eigen Man ha deciso che perdonerà Capitan Numerica solo se quest’ultimo risolverà il quesito seguente. Sia \(p\) un primo positivo per cui esistono \(m,n\) interi tali che \(p/m,\varphi(m)/n\), e \(\varphi(n)/m\), dove \(\varphi\) indica la funzione φ di Eulero". [...]

Qual è la domanda?

[Sdavas]

Scusate, viene richiesta la somma dei numeri primi p che verificano la condizione: "Sia p un primo positivo per cui esistono m,n interi tali che p | m, φ(m) | n, e φ(n) | m".
Grazie.

[dan952]

Un po' di considerazioni:

- Se $n>2$ allora $\phi(n)$ è pari.

- Se $m$ e $n$ sono coprimi allora $\phi(m)\phi(n)=\phi(mn)$ (funzione moltiplicativa)


Ora siano $m=2^{\alpha}a$ e $n=2^{\beta}b$ [nota]Dove $\alpha$ e $\beta$ sono gli esponenti massimi di $2$ in $m$ e $n$ rispettivamente (si scrive $2^{\alpha}||m$).[/nota]allora si ha

$\phi(m)=\phi(2^{\alpha})\phi(a)$

$\phi(n)=\phi(2^{\beta})\phi(b)$

Ora abbiamo detto che per $n>2$ segue che $\phi(n)$ è pari, quindi supponendo $a, b>2$ esistono $2^{h_1}||\phi(a)$ e $2^{h_2}|| \phi(b)$, inoltre si deve avere che

$\phi(2^{\beta})\phi(b)|m$

$\phi(2^{\alpha})\phi(a)|n$

Dunque

$2^{\beta-1+h_1}|2^{\alpha}$

$2^{\alpha-1+h_2}|2^{\beta}$

Ovvero

$\alpha-\beta-h_1+1 \geq 0$

$\beta-\alpha-h_2+1 \geq 0$

Da cui

$2-(h_1+h_2) \geq 0$

I possibili valori sono (WLog per simmetria)

$h_1=h_2=0$)
Segue che 2 è l' unico fattore primo di entrambi

$h_1=0$ e $h_2=1$)
Segue facilmente che l'unico fattore primo dispari è 3

$h_1=h_2=1$)
Segue facilmente che 3 e 7 sono gli unici fattori primi dispari

$h_1=2$ e $h_2=0$
Segue facilmente che 5 è l'unico fattore primo dispari

Quindi $2+3+5+7=17$.