Equazioni con il totiente

[stefanos]

Trovare i valori di $ $n$ $ per cui:
1. $ $\phi(n) = \frac{n}{2}$ $ ?
2. $ $\phi(n) = \phi(2n)$ $ ?
3. $ $\phi(n) = 12$ $ ?

[String]

Provo per ora il punto 1... Dato che $ \phi (n)=\displaystyle \frac {n}{2} $ ho pensato che n deve essere pari. Quindi affinchè la condizione sia soddisfatta occorre che tutti i numeri dispari siano coprimi con n e ciò accade se n è una potenza di 2... è giusto?

[SkZ]

$ $\frac{n}{2}=n\frac{1}{2}=n(1-\frac{1}{2})$ $ direi che torna

[exodd]

per il secondo punto
$ \phi(2n)=\phi(n)*\phi(2)=\phi(n) $
solo se MCD tra due e n è 1, cioè solo se n è dispari...

spero di non aver scritto una castroneria...

[EvaristeG]

Cari, invece di finire i messaggi con cose del tipo "spero che sia giusto", "spero che torni" e cose simili, potreste scrivere delle dimostrazioni di quello che dite, eh?
Se fosse un esercizio di cesenatico o simili, queste soluzioni varrebbero un punto o due... se, come credo e spero, non avete sparato il risultato a caso, che vi costa scrivere come vi è venuto fuori?

[stefanos]

String, a me viene lo stesso risultato. Io l'ho dimostrato cosi': parto dall'identita' $ $\phi(n) = n \prod_{p|n} \left(1-\frac{1}{p}\right)$ $, riscrivo quindi la relazione data, semplifico, e arrivo a $ $2 \prod_{p|n} (p - 1) = \prod_{p|n} p$ $.
Vedo (modulo 2) che uno dei fattori deve essere un $ $2$ $. Posto $ $p_1 = 2$ $ e riscritta la relazione, ottengo nel LHS il prodotto di termini pari (primi dispari - 1) e nel RHS il prodotto di termini tutti dispari (sono tutti primi): cio' significa che non ci sono fattori diversi da $ $2$ $.
Ci sono degli errori in questa dimostrazione?

exodd: ho fatto anche io cosi'

[killing_buddha]

Sia
(1) $ \qquad\displaystyle\phi(n)-\frac{n}{2}=0 $

vediamo che le potenze di due sono tutte e sole le soluzioni di (1).
Tutte:
$ \displaystyle\phi(2^k)=2^k-2^{k-1} =2^{k-1} = \frac{2^k}{2} $
questo vale per ogni $ ~k\in\mathbb{N} $.
Sole:
Supponiamo $ ~n\neq 2^k $, dunque $ ~n=2^j r $ con $ ~j,r\in\mathbb{N} $ ed $ ~r=p_1^{m_1}\dots p_s^{m_s} $. Si avrebbe
$ \displaystyle 2^{j-1}p_1^{m_1}\dots p_s^{m_s}= $
$ \quad (2^{j-1})\phi(r)=\quad (2^{j-1})(p_1^{m_1}-p_1^{m_1-1})\dots(p_s^{m_s}-p_s^{m_s-1}) $
ma ciò non e possibile per unicità della fattorizzazione di $ ~n $.
QED

[String]

Provo il punto 3, ma non sono riuscito a dare una vera dimostrazione e per di più è anche un casino bestiale...
Consideriamo prima i valori dispari di n. Allora $ n>12 $. E' facile vedere che la condizione è soddisfatta per $ n=13 $ essendo primo, e inoltre per quanto dimostrato prima sarà soluzione anche $ 2n $ cioè$ 26 $. Ora, escludendo gli altri primi si trova un'altra soluzione per $ n=21 $ e di conseguenza anche per $ n=42 $. Se $ n>32 $ allora si possono escludere anche gli altri dispari perchè oltre alle potenze di 2,1, e n-1, ci sono almeno 3 primi con i rispettivi doppi.
Consideriamo adesso i valori di n pari. Vediamo che avendo escluso i valori dispari di n, escludiamo di conseguenza anche i rispettivi $ 2n $ e quindi rimangono da verificare solo i pari multipli di 4. Essi devono essere $ >24 $. Sappiamo inoltre che n non può essere una potenza di 2 perchè ha la metà di numeri primi con esso.
Ora se considero $ n<40 $, esso sarà dato dal prodotto tra 4 e un altro numero che può essere quindi 7 o 9.
Nel primo caso si deve avere:
$ $ \frac {4\cdot 7}{2}- \frac {4\cdot 7}{14}=12 $ che è vera e quindi 28 è un altro possibile valore di n.
Nel secondo caso invece si deve avere:
$ $ \frac {36}{2}-\frac {36}{6}=12 $ vera anche in questo caso e quindi aggiungiamo anche 36.
Consideriamo adesso i valori di n ottenuti moltiplicando 4 e un numero primo e vediamo che non sono accettabili perchè $ 4p-4=24 $
Se invece n è dato da 4 per un numero del tipo 2p allora si avrebbe
$ 4p-4=12 $ che non può essere, e quindi a maggior ragione non potrà essere $ 4\cdot 4p,6p,8p... $
Infine se n è dato dal prodotto tra 4 e due numeri primi ad esempio
$ 4\cdot 3\cdot 5=60 $, ripetendo lo stesso ragionamento di prima
$ $ \frac {60}{2}-\frac {60}{6}-\frac {60}{10}+\frac {60}{30}=12 $ che non è vera e perciò non sarà vera neppure
$ 4\cdot 3\cdot 7=84 $. Infatti si toglierà una stessa quantità tolta dal numero di prima (in questo caso 6) ma da un numero maggiore, e una quantità più grande ma che in realtà toglie la stessa quantità di prima (10) più i divisori di 6 compresi tra 84 e 60 cioè 4. Con questo ragionamento si può andare all'infinito e vedere che non saranno soluzioni neanche
$ 4\cdot 5\cdot 7 $, $ 4\cdot 5\cdot 9 $, $ 4\cdot 7\cdot 11 $ e così via. Se i numeri non sono primi, si prendono in considerazione sempre i primi di cui sono formati
Quindi ricapitolando n=13,26,21,42,28,36
Lo so è bruttissima, ma non so fare di meglio, sicuramente avrete tutti una soluzione più decente... Spero almeno di non aver detto cavolate....[/tex]

[stefanos]

Allora, io dimostro che le soluzioni del punto 3 sono quelle trovate da String, 13, 21, 26, 28, 36, 42. Mi scuso subito per il procedimento un po' lungo =/

Parto ancora dall'identita` $ $\phi(n) = n \prod_{p|n} \frac{p-1}{p} = 12$ $. La scrivo in una forma migliore: $ $n \prod_{p|n} (p-1) = 2^2 \cdot 3 \prod_{p|n} p$ $.
Divido la dimostrazione in due parti: prima mi occupo dei numeri dispari, poi di quelli pari.


Parte (i): numeri dispari.

Nel RHS ci sono chiaramente solo due fattori pari ($ $2^2$ $), quindi cosi` deve essere anche nel LHS; noto inoltre che tutti i fattori (eccetto $ $n$ $) che compaiono nel LHS sono pari. Ora, ci sono due modi in cui la condizione della divisibilita` (esatta) per $ $4$ $, nel LHS, puo` essere rispettata: o $ $n = p^\alpha q^\beta$ $, dove i due fattori primi sono entrambi congrui a $ $3 \pmod 4$ $ (cosicche` i termini $ $p-1, q-1$ $ contengano ciascuno un fattore $ $2$ $), oppure $ $n = p^\alpha, p \equiv 5 \pmod 8$ $ (e quindi $ 4 || $p - 1$ $, cioe` divide esattamente).

Primo caso:
Pongo $ $n = p^\alpha q^\beta$ $: ho quindi $ $p^\alpha q^\beta (p-1) (q-1) = 2^2 \cdot 3 pq$ $, da cui ottengo $ $p^{\alpha-1} q^{\beta-1} \frac{p-1}{2} \frac{q-1}{2} = 3$ $. E` chiaro che solo uno dei fattori e` diverso da $ $1$ $: esaminando i casi possibili (escludendo il caso in cui $ $p = q$ $) trovo che l'unica soluzione e` $ $n = 3 \cdot 7 = 21$ $.

Secondo caso:
Pongo $ $n = p^\alpha$ $, e riscrivo l'equazione di partenza: $ $p^{\alpha-1} \frac{p-1}{4} = 3$ $. Come prima, solo uno dei fattori e` diverso da $ $1$ $: si vede facilmente che l'unica soluzione e` $ $n = 13$ $. Ho trovato tutte le soluzioni dispari.


Parte (ii): numeri pari.

Allora, pongo $ $p_1 = 2$ $ e riscrivo l'equazione ($ $\alpha$ $ e` l'esponente di questo fattore nella fattorizzazione di $ $n$ $):
$ $2^\alpha p_2^{\alpha_2} \cdots p_k^{\alpha_k} (p_2-1) \cdots (p_k-1) = 2^3 \cdot 3 \cdot p_2 \cdots p_k$ $.
Studio i fattori pari: nel RHS ho esattamente tre fattori $ $2$ $, quindi cosi` deve essere anche nel LHS; chiamo $ $d_i := z : 2^z || p_i - 1$ $: e` chiaro che la massima potenza di $ $2$ $ che divide il LHS e` $ $2^{\alpha + \sum_{i=2}^k d_i}$ $. Dunque, $ $3 = \alpha + \sum_{i=2}^k d_i$ $, ovvero $ $3-\alpha = \sum_{i=2}^k d_i$ $. Non e` difficile notare che il membro di sinistra deve essere positivo, quindi analizzo tre casi ($ $\alpha > 0$ $, perche` $ $2|n$ $).

Primo caso: $ $\alpha = 1$ $
Quindi $ $2 = \sum_{i=2}^k d_i$ $; i $ $d_i$ $ sono tutti strettamente positivi, quindi questa condizione impone uno dei seguenti sotto-casi:

1. Ci sono due fattori primi nella fattorizzazione di $ $n$ $, oltre al $ $2$ $, e sono entrambi congrui a $ $3 \pmod 4$ $.

Pongo $ $n = 2p^\alpha q^\beta$ $, sostituisco e trovo $ $2 p^\alpha q^\beta (p-1) (q-1) = 2^3 \cdot 3 \cdot pq $ $; quindi $ $p^{\alpha-1} q^{\beta-1} \frac{p-1}{2} \frac{q-1}{2} = 3$ $. Questa equazione e` identica a quella trovata nel primo caso della prima parte, e tenendo conto del fattore $ $2$ $ la soluzione e` $ $n = 42$ $.

2. C'e` un solo fattore, oltre al $ $2$ $, nella fattorizzazione di $ $n$ $, e questo e` congruo a $ $5 \pmod 8$ $; pongo $ $n = 2p^\alpha$ $ e sostituisco: $ $2p^\alpha (p-1) = 2^3 \cdot 3 \cdot p$ $. Allora, $ $p^{\alpha-1} \frac{p-1}{4} = 3$ $: l'unica soluzione e` $ $n = 26$ $

Secondo caso: $ $\alpha = 2$ $
Quindi $ $1 = \sum_{i=2}^k d_i$ $. Per ragioni analoghe a quelle esposte precedentemente, ci deve essere un solo fattore, oltre al $ $2$ $, nella fattorizzazione di $ $n$ $.
Pongo allora $ $n = 2^2 p^\alpha$ $, e trovo $ $2^2 p^\alpha (p-1) = 2^3 \cdot 3 \cdot p$ $, da cui $ $p^{\alpha-1} \frac{p-1}{2} = 3$ $. Ora, o $ $\frac{p-1}{2} = 3$ $, e cioe` $ $p = 7$ $, e $ $\alpha = 1$ $ (da cui ottengo la soluzione $ $n = 28$ $), oppure $ $p = 3, \alpha = 2$ $, e trovo la soluzione $ $n = 36$ $.

Cosi` ho trovato anche tutte le soluzioni pari, e ho concluso la dimostrazione (corretta?)