Trovare gli elementi invertibili di un anello Zn

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Trovare gli elementi invertibili di un anello Zn #59943

avt
mandarino
Punto
Salve a tutti, il mio problema è determinare gli elementi invertibili di un anello Zn, per esempio dell'anello \left(Z_{8},+,\cdot  \right) e in seguito calcolare l'inverso di ogni elemento invertibile.

Allora io riesco a trovarmi quante sono le classi invertibili tramite la funzione di Eulero e meccanicamente calcolarmi ogni MCD e trovare il valore di ogni classe invertibile, in questo caso (1,3,5,7). Questo metodo funziona per numeri piccoli ma come mi comporto con numeri grandi? Tramite la funzione di Eulero posso calcolarmi senza problemi quante classi ci sono in Zn ma per determinarle tutte e poi calcolane l'inverso qual'è il modo più veloce?

Spero di essere stato chiaro, grazie a tutti per l'aiuto.
 
 

Trovare gli elementi invertibili di un anello Zn #60031

avt
Galois
Coamministratore
Ciao Mandarino emt

Come ben dici, per determinare quanti sono gli elementi (le classi) invertibili dell'anello \mathbb{Z}_n possiamo far ricorso alla funzione di Eulero che, grazie alle sue proprietà ci permette di trovare abbastanza agevolmente il numero cercato.

Per quanto riguarda: quali sono tali elementi, che io sappia, non esiste una vera e propria "regola". Possiamo però far ricorso ai criteri di divisibilità.

Ricordiamo infatti che gli elementi invertibili dell'anello \mathbb{Z}_n sono classi di equivalenza \left[a\right]_n tali che mcd(a,n)=1

ovvero a deve essere primo con n, cioè a non deve essere un divisore di n.

Per farti un esempio, se abbiamo l'anello \mathbb{Z}_{256}, allora il numero dei suoi elementi invertibili è:

\phi(256)=\phi(2^8)=2^8\left(1-\frac{1}{2}\right)=2^8 \cdot \frac{1}{2}=2^7=128

Ora, essendo, la fattorizzazione in primi di 256=2^6

allora le classi invertibili \left[a\right]_{256} saranno tali che a sarà un numero non divisibile per 2, ovvero un numero dispari. Saranno quindi tutte e sole del tipo:

\left[2k-1\right]_{256}

con 1 \leq k \leq 128

Per trovare l'inverso, puoi far ricorso all'algoritmo della divisione euclidea (a ritroso) oppure utilizzare il barbatrucco spiegato in questo topic: come trovare gli elementi invertibili in Zn

ma entrambi son procedimenti abbastanza lunghi.. Sfido qualunque prof a mettere un esercizio del genere con n molto grande emt
Ringraziano: Omega, CarFaby, mandarino

Re: Trovare gli elementi invertibili di un anello Zn #60125

avt
mandarino
Punto
Grazie sei stato molto chiaro! emt

Io per calcolare la funzione di Eulero uso il seguente metodo, chiedo conferma se può funzionare sempre:

\varphi (256)=2^{8}=(2^8-2^7)=128

Puoi spiegarmi gentilmente come usare l'algoritmo Euclideo per trovare ogni inverso? (premetto che so utilizzare l'algoritmo come per esempio nelle equazioni diofantee e nelle congruenze)

Inoltre se me lo permettete avrei bisogno di un chiarimento su un esercizio di esame, (so che non è consetito riportare il testo ma spero possiate perdonarmi)

- Negli anelli Z_{14} calcolare i rispettivi gruppi di elementi invertibili.

U(Z_{14}):=\left\{\overline{z} \in Z_{14} | \exists   \overline{z}^{-1} \in Z_{14} : \overline{z}  \cdot \overline{z}^{-1} = \overline{1} \right\}\right\}

Non riesco a capire bene cosa chiede l'esercizio! emt

Re: Trovare gli elementi invertibili di un anello Zn #60155

avt
Galois
Coamministratore
Io per calcolare la funzione di Eulero uso il seguente metodo, chiedo conferma se può funzionare sempre:

\varphi (256)=2^{8}=(2^8-2^7)=128



Certo che vale sempre! Ti faccio notare infatti che è la stessa identica formula che ho utilizzato io nel primo post.

Si dimostra infatti che, se p è un primo:

\varphi (p)=p^n \left(1-\frac{1}{p}\right)

eseguendo il prodotto a secondo membro, tale formula puoi scriverla anche come:

\varphi (p)=p^n - p^{n-1}

quindi non cambia nulla emt

Puoi spiegarmi gentilmente come usare l'algoritmo Euclideo per trovare ogni inverso?


Prendiamo ad esempio l'anello \mathbb{Z}_{18}. Sappiamo che un suo elemento invertibile è, ad esempio, la classe:

\left[5\right]_{18} := \overline{5}

in quanto mcd(5,18)=1

Proponiamoci ora di trovare l'inverso, ovvero l'elemento, che chiamerò \overline{z}^{-1} tale che 5z^{-1} \equiv 1 \ (mod \ 18)

Poiché mcd(5,18)=1, esistono u,v \in \mathbb{Z} tali che:

5u+18v=1

Troviamoli con l'algoritmo di Bezout.

18 = 5 \cdot 3 + 3

5 = 1 \cdot 3 + 2

3= 2 \cdot 1 + 1

2= 1 \cdot 2 + 0

Procedendo a ritroso a partire dalla penultima uguaglianza, esplicitando di volta in volta i resti troviamo:

1= 3-2\cdot 1 = .... = 2 \cdot 18 - 7 \cdot 5

Da cui:

u=-7 e v=2

Ora, sappiamo che:

5u+18v=1

ciò significa che:

18v=1-5u ovvero: 18 | (1-5u) che per definizione di congruenza equivale a dire che:

5u \equiv 1 \ (mod \ 18)

Ovvero u=-7=11 \ (mod 18)

è proprio il nostro inverso moltiplicativo emt

Negli anelli Z_{14} calcolare i rispettivi gruppi di elementi invertibili.

U(Z_{14}):=\left\{\overline{z} \in Z_{14} | \exists   \overline{z}^{-1} \in Z_{14} : \overline{z}  \cdot \overline{z}^{-1} = \overline{1} \right\}

Non riesco a capire bene cosa chiede l'esercizio


Per quanto mi riguarda c'è qualcosa che non va nella traccia! In particolare il fatto che venga usato il plurale.. "calcolare i rispettivi gruppi di elementi invertibili". Il gruppo di elementi invertibili è infatti uno (ed uno solo).

A parte questo (se la traccia è davvero questa ti invito a chiedere delucidazioni al tuo prof per capire se è o meno un errore di battitura - altrimenti non saprei spiegarlo - ) la risposta al tuo esercizio, ovvero trovare il gruppo degli elementi invertibili di Z_{14} sta nel mio precedente post. Ricito:

Ricordiamo infatti che gli elementi invertibili dell'anello \mathbb{Z}_n sono classi di equivalenza \left[a\right]_n tali che mcd(a,n)=1

Nel nostro caso n=14.

Pertanto gli elementi invertibili saranno le classi \overline{a}:=\left[a\right]_{14} tali che mcd(a,14)=1, ovvero:

U(Z_{14})=\left\{\overline{1}, \ \overline{3}, \ \overline{5}, \ \overline{9}, \ \overline{11}, \ \overline{13}  \right\}
Ringraziano: mandarino, dany.collu
  • Pagina:
  • 1
Os