(facile facile)
Trovare tutti gli interi positivi n tali che in $ \mathbb{Z}_n $ ogni elemento invertibile sia uguale al proprio inverso.
Tutti uguali al proprio inverso
Hmm non fate confusione : penso che per elemento invertibile si intenda con inverso rispetto alla moltiplicazione, quindi si chiede per quali n si ha $ (x,n)=1 \Rightarrow x^2\equiv 1 (\bmod n) $.
Ad esempio, modulo 4 funziona :
1^2=1 (4), 3^2=9=1 (4)
Oppure ho capito male anch'io??
Ad esempio, modulo 4 funziona :
1^2=1 (4), 3^2=9=1 (4)
Oppure ho capito male anch'io??
Ultima modifica di EvaristeG il 29 mag 2006, 21:59, modificato 1 volta in totale.
-
ubermensch
- Messaggi: 49
- Iscritto il: 17 ott 2005, 21:53
Dunque si cercano gli $ n $ tali che $ x^2\equiv1(n)\forall x\in Z_n $.
Per cui innanzitutto deve essere $ \varphi(n)=2^k $, perchè altrimenti dal teorema di Cauchy vi sarebbero in $ Z_n $ elementi di ordine un qualche altro primo. La condizione sulla funzione di Eulero equivale a richiedere che $ n=2^r3^t,t\in\{0,1\},r\in Z $. Sia ora $ U(n) $ il gruppo degli invertibili di $ Z_n $, nel nostro caso abbiamo $ U(n)=Z_2\times Z_{2^{r-2}}\times Z_2 $ (dove abbiamo escluso il caso r=1,2 essendo la tesi evidentemente vera). Per cui in definitiva gli unici n possibili sono $ n=1,2,3,4,6,8,12,24 $
Per cui innanzitutto deve essere $ \varphi(n)=2^k $, perchè altrimenti dal teorema di Cauchy vi sarebbero in $ Z_n $ elementi di ordine un qualche altro primo. La condizione sulla funzione di Eulero equivale a richiedere che $ n=2^r3^t,t\in\{0,1\},r\in Z $. Sia ora $ U(n) $ il gruppo degli invertibili di $ Z_n $, nel nostro caso abbiamo $ U(n)=Z_2\times Z_{2^{r-2}}\times Z_2 $ (dove abbiamo escluso il caso r=1,2 essendo la tesi evidentemente vera). Per cui in definitiva gli unici n possibili sono $ n=1,2,3,4,6,8,12,24 $
@ubermensch: arrivi alla soluzione giusta, ma con una dimostrazione fallata: tu sostieni che gli unici numeri che hanno per phi una potenza di due sono solo della forma $ 2^a 3^b $. Come la mettiamo con 5, 17, 257, 65537? Poi, che questi non vadano bene, siamo d'accordo, ma dovresti escluderli diversamente...
...e trovare una soluzione un po' meno Algebra I e un po' più Olimpiadi della Matematica?
...e trovare una soluzione un po' meno Algebra I e un po' più Olimpiadi della Matematica?
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
ubermensch
- Messaggi: 49
- Iscritto il: 17 ott 2005, 21:53
hai ragione Marco, mi sono dimenticato i primi $ p $ tali che $ p-1 $ è una potenza di 2, i quali possono comparire in n solo alla prima potenza e quindi andando a vedere il loro contributo al gruppo degli invertibili sarà qualcosa del tipo
$ Z_{2^t} $ e quindi t=1 e p=3.
Sono stato un pò conciso, ma credo che abbiate capito (vado di fretta)
P.S.scusate l'eresia ma non avendo mai fatto un'olimpiade di matematica non ho idea di quale sia la differenza fra una dimostrazione olimpica e una non olimpica
$ Z_{2^t} $ e quindi t=1 e p=3.
Sono stato un pò conciso, ma credo che abbiate capito (vado di fretta)
P.S.scusate l'eresia ma non avendo mai fatto un'olimpiade di matematica non ho idea di quale sia la differenza fra una dimostrazione olimpica e una non olimpica
Io mi ero dimenticato il 24 però le cose non si complicano molto.
Questa era la mia dimostrazione:
Dobbiamo trovare tutti gli $ a $ tali che $ n^2-1=(n+1)(n-1)\equiv 0 \pmod a \forall n \in \mathbb{Z}_a $.
Supponiamo che $ p | a, p \ge 5 $. Allora esiste k tale che $ k \not \equiv 0, k-1 \not \equiv 0, k+1 \not \equiv 0 \pmod p $. Dimostriamo che esiste anche un k' che soddisfa questa relazione ed è primo con a.
Se a si scompone in $ a=p \cdot altriprimi $, si imposta il sistema:
$ \begin{cases} k' \equiv k \pmod p \\ k' \not \equiv \pmod {altriprimi}\\ \end{cases} $
Che per il teorema cinese ha almeno una soluzione.
Ma quindi k' sarebbe invertibile, ma k-1 e k+1 non contengono fattori p, quindi il suo inverso è diverso da se stesso (altrimenti $ (k'+1)(k'-1)\equiv 0 \pmod a $
Ho trascurato gli esponenti che puo avere p, però se non vale per $ p^1 $ non vale neanche per $ p^n $.
Quindi ci restano solo i casi in cui a contiene solo i fattori 2 e 3.
Si verifica subito che con 2 funziona solo fino a 8, mentre già con 16 3 è un controesempio (e lo è anche per tutte le potenze maggiori).
Per $ 3^b, b \ge 2 $ si dimostra che non funziona allo stesso modo di prima.
I restanti casi sono validi.
Il modo più rapido per farlo comunque era osservare questo:
$ n^2 \equiv 1 \pmod a \Rightleftarrow (n+1)(n-1) \equiv 0 \pmod a $.
Si osserva che, preso un modulo dispari > 3, già 2 è sempre un controesempio, mentre 3 funziona.
Se prendiamo un modulo a pari, per ogni n dispari (condizione necessaria perchè sia primo con a), sia (n-1) sia (n+1) sono pari, inoltre uno e solo uno è multiplo di 4. Quindi se a contiene il fattore 8, va bene.
Se $ a=2^n\cdot 3 $, per ogni non multiplo di tre, uno tra (n+1) e (n-1) non lo è.
Se a contiene primi maggiori di 3, o potenze di 3 con esponente >= 2, questo non è assicurato. Ma siamo sicuri che esista sempre un controesempio che sia primo con a? Si, grazie al teorema cinese del resto.
In conclusione sono: 1,2,3,4,6,8,12,24.
P.s. ho scritto facile facile perchè è il primo problema che posto e quindi cercavo di prevenirmi da eventuali figuracce
Questa era la mia dimostrazione:
Dobbiamo trovare tutti gli $ a $ tali che $ n^2-1=(n+1)(n-1)\equiv 0 \pmod a \forall n \in \mathbb{Z}_a $.
Supponiamo che $ p | a, p \ge 5 $. Allora esiste k tale che $ k \not \equiv 0, k-1 \not \equiv 0, k+1 \not \equiv 0 \pmod p $. Dimostriamo che esiste anche un k' che soddisfa questa relazione ed è primo con a.
Se a si scompone in $ a=p \cdot altriprimi $, si imposta il sistema:
$ \begin{cases} k' \equiv k \pmod p \\ k' \not \equiv \pmod {altriprimi}\\ \end{cases} $
Che per il teorema cinese ha almeno una soluzione.
Ma quindi k' sarebbe invertibile, ma k-1 e k+1 non contengono fattori p, quindi il suo inverso è diverso da se stesso (altrimenti $ (k'+1)(k'-1)\equiv 0 \pmod a $
Ho trascurato gli esponenti che puo avere p, però se non vale per $ p^1 $ non vale neanche per $ p^n $.
Quindi ci restano solo i casi in cui a contiene solo i fattori 2 e 3.
Si verifica subito che con 2 funziona solo fino a 8, mentre già con 16 3 è un controesempio (e lo è anche per tutte le potenze maggiori).
Per $ 3^b, b \ge 2 $ si dimostra che non funziona allo stesso modo di prima.
I restanti casi sono validi.
Il modo più rapido per farlo comunque era osservare questo:
$ n^2 \equiv 1 \pmod a \Rightleftarrow (n+1)(n-1) \equiv 0 \pmod a $.
Si osserva che, preso un modulo dispari > 3, già 2 è sempre un controesempio, mentre 3 funziona.
Se prendiamo un modulo a pari, per ogni n dispari (condizione necessaria perchè sia primo con a), sia (n-1) sia (n+1) sono pari, inoltre uno e solo uno è multiplo di 4. Quindi se a contiene il fattore 8, va bene.
Se $ a=2^n\cdot 3 $, per ogni non multiplo di tre, uno tra (n+1) e (n-1) non lo è.
Se a contiene primi maggiori di 3, o potenze di 3 con esponente >= 2, questo non è assicurato. Ma siamo sicuri che esista sempre un controesempio che sia primo con a? Si, grazie al teorema cinese del resto.
In conclusione sono: 1,2,3,4,6,8,12,24.
P.s. ho scritto facile facile perchè è il primo problema che posto e quindi cercavo di prevenirmi da eventuali figuracce
Ok. La soluzione di edriv funziona (anche se qui e là non è chiarissimo quello che dici...). Faccio notare che c'è un teoremino di Teoria dei Numeri, perfettamente utilizzabile in ambito olimpico:
Teorema (dell'Elemento Primitivo): Se p è un numero primo, allora esiste a una classe mod p, t.c. a ha ordine moltiplicativo p-1 (mod. p).
In altri termini, esiste una classe le cui potenze coprono tutti gli elementi mod p diversi da 0. Notare che p-1 è il massimo possibile, in virtù del Piccolo Teorema di Fermat. Il T.E.P. dice che il massimo è sempre raggiunto per ogni primo p.
Es.: p=17. Un elemento primitivo è 3: le potenze di 3 sono (mod 17):
3, -8, -7, -4, 5, -2, -6, -1, -3, 8, 7, 4, -5, 2, 6, 1. [16 numeri distinti!].
Applichiamolo al nostro problema: dato un qualunque primo p>3, esiste un elemento che ha ordine p-1. Gli elementi il cui inverso sia sé stesso possono avere solo ordine 1 o 2, quindi il T.E.P. mi dà subito l'esistenza di un controesempio.
I casi 3 e 2 si fanno a parte come hanno fatto vedere gli altri.
Teorema (dell'Elemento Primitivo): Se p è un numero primo, allora esiste a una classe mod p, t.c. a ha ordine moltiplicativo p-1 (mod. p).
In altri termini, esiste una classe le cui potenze coprono tutti gli elementi mod p diversi da 0. Notare che p-1 è il massimo possibile, in virtù del Piccolo Teorema di Fermat. Il T.E.P. dice che il massimo è sempre raggiunto per ogni primo p.
Es.: p=17. Un elemento primitivo è 3: le potenze di 3 sono (mod 17):
3, -8, -7, -4, 5, -2, -6, -1, -3, 8, 7, 4, -5, 2, 6, 1. [16 numeri distinti!].
Applichiamolo al nostro problema: dato un qualunque primo p>3, esiste un elemento che ha ordine p-1. Gli elementi il cui inverso sia sé stesso possono avere solo ordine 1 o 2, quindi il T.E.P. mi dà subito l'esistenza di un controesempio.
I casi 3 e 2 si fanno a parte come hanno fatto vedere gli altri.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
ubermensch
- Messaggi: 49
- Iscritto il: 17 ott 2005, 21:53
scusami Marco, certamente non voglio fare polemica, ma solo cercare di capire qual è la distinzione fra ambito olimpico e non: il teorema che hai enunciato afferma, di fatto, che $ Z/2Z $ è ciclico. E va bene... però con questo risultato da
solo non mi sembra che ci si faccia gran che: bisogna sapere che per $ n $qualsiasi il gruppo moltiplicativo si spezza nel modo noto...
quindi quello che voglio dire e che la mia soluzione e la tua, sono praticamente uguali...
solo non mi sembra che ci si faccia gran che: bisogna sapere che per $ n $qualsiasi il gruppo moltiplicativo si spezza nel modo noto...
quindi quello che voglio dire e che la mia soluzione e la tua, sono praticamente uguali...
Rispondo volentieri a questa domanda, perché mi permette di chiarire quello che, secondo me, è olimpico e quello che non lo è. Va detto che spesso, come qui, la linea di demarcazione non è affatto netta, quindi non pretendo di avere ragione al 100%.
Il Teorema dell'Elemento Primitivo è argomento olimpico (nel senso che ogni tanto compare in qualche gara e che agli stages viene citato), ovviamente nella forma che si applica a oggetti olimpicamente leciti, per così dire... (interi modulo p, ok; campi finiti in genere no...).
Il fatto che citi che i gruppi moltiplicativi di moduli coprimi sono scomponibili in prodotto diretto è, in fin dei conti, solo un modo sofisticato (e complicato) di applicare il Teorema Cinese del Resto (e qui non ci sono dubbi, che siamo in pieno ambito olimpico).
La mia contestazione sulla tua sol. è, che se non citi esplicitamente che i primi >3 hanno elementi di ordine >2, le considerazioni sulla phi non ti bastano per escluderli. Inoltre, il linguaggio è chiaramente quello dei corsi universitari, quando la stessa identica soluzione si poteva fare con il Teorema Cinese del Resto e senza introdurre i gruppi Zn* (insomma, in un linguaggio volendo comprensibile anche ai quei poveri studenti pre-universitari che dovessero passare da queste parti).
Infine: perché ho citato il T.E.P. (che era in fin dei conti il tassello mancante della tua sol.)? Perché il buon Edriv ha dovuto arrampicarsi sugli specchi per provare che esiste k' coprimo con a ecc ecc, quando, se avesse saputo del teorema, si sarebbe risparmiato qualche acrobazia.
Insomma, per farla breve, la tua dimostrazione annegava un fatto olimpico di uan certa importanza in una forma inaccessibile ad un potenziale concorrente olimpico; ho voluto semplicemente cogliere l'occasione per segnalare un risultato potente e non notissimo.
Il Teorema dell'Elemento Primitivo è argomento olimpico (nel senso che ogni tanto compare in qualche gara e che agli stages viene citato), ovviamente nella forma che si applica a oggetti olimpicamente leciti, per così dire... (interi modulo p, ok; campi finiti in genere no...).
Il fatto che citi che i gruppi moltiplicativi di moduli coprimi sono scomponibili in prodotto diretto è, in fin dei conti, solo un modo sofisticato (e complicato) di applicare il Teorema Cinese del Resto (e qui non ci sono dubbi, che siamo in pieno ambito olimpico).
La mia contestazione sulla tua sol. è, che se non citi esplicitamente che i primi >3 hanno elementi di ordine >2, le considerazioni sulla phi non ti bastano per escluderli. Inoltre, il linguaggio è chiaramente quello dei corsi universitari, quando la stessa identica soluzione si poteva fare con il Teorema Cinese del Resto e senza introdurre i gruppi Zn* (insomma, in un linguaggio volendo comprensibile anche ai quei poveri studenti pre-universitari che dovessero passare da queste parti).
Infine: perché ho citato il T.E.P. (che era in fin dei conti il tassello mancante della tua sol.)? Perché il buon Edriv ha dovuto arrampicarsi sugli specchi per provare che esiste k' coprimo con a ecc ecc, quando, se avesse saputo del teorema, si sarebbe risparmiato qualche acrobazia.
Insomma, per farla breve, la tua dimostrazione annegava un fatto olimpico di uan certa importanza in una forma inaccessibile ad un potenziale concorrente olimpico; ho voluto semplicemente cogliere l'occasione per segnalare un risultato potente e non notissimo.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
ubermensch
- Messaggi: 49
- Iscritto il: 17 ott 2005, 21:53
ok, Marco, ti ringrazio per il chiarimento..
probabilmente ho interpretato male lo spirito di questo forum: avendo piena consapevolezza della vostra validità mi è sembrato opportuno dare una soluzione
"universitaria" e dare per scontati alcuni concetti, come ad esempio il fatto che primi >3 hanno elementi di periodo >2 (th di Cauchy se p-1 non è potenza di 2 e la scomposizione mediante prod diretto nell'altro caso)...
la prossima volta starò più attento...
Saluti
probabilmente ho interpretato male lo spirito di questo forum: avendo piena consapevolezza della vostra validità mi è sembrato opportuno dare una soluzione
"universitaria" e dare per scontati alcuni concetti, come ad esempio il fatto che primi >3 hanno elementi di periodo >2 (th di Cauchy se p-1 non è potenza di 2 e la scomposizione mediante prod diretto nell'altro caso)...
la prossima volta starò più attento...
Saluti