Equazioni con il totiente
Equazioni con il totiente
Trovare i valori di $ $n$ $ per cui:
1. $ $\phi(n) = \frac{n}{2}$ $ ?
2. $ $\phi(n) = \phi(2n)$ $ ?
3. $ $\phi(n) = 12$ $ ?
1. $ $\phi(n) = \frac{n}{2}$ $ ?
2. $ $\phi(n) = \phi(2n)$ $ ?
3. $ $\phi(n) = 12$ $ ?
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?
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)
ma per seguir virtute e canoscenza"(Dante)
- exodd
- Messaggi: 728
- Iscritto il: 09 mar 2007, 19:46
- Località: sulle pendici della provincia più alta d'europa
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...
$ \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...
Tutto è possibile: L'impossibile richiede solo più tempo
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
ispiratore del BTAEvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
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?
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?
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'
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'
-
- Messaggi: 209
- Iscritto il: 20 mag 2007, 12:39
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
(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
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]
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]
Ultima modifica di String il 13 ago 2008, 18:56, modificato 3 volte in totale.
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)
ma per seguir virtute e canoscenza"(Dante)
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?)
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?)